Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes
Locally Decodable Codes (LDCs) are error-correcting codes $C\colonΣ^n\rightarrow Σ^m,$ encoding \emph{messages} in $Σ^n$ to \emph{codewords} in $Σ^m$, with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best construction...
Պահպանված է:
| Հիմնական հեղինակներ: | , , , , , , |
|---|---|
| Ձևաչափ: | Հոդված |
| Հրապարակվել է: |
2026
|
| Խորագրեր: | |
| Առցանց հասանելիություն: | https://arxiv.org/abs/2602.20278 http://arxiv.org/abs/2602.20278 |
| Ցուցիչներ: |
Չկան պիտակներ, Եղեք առաջինը, ով նշում է այս գրառումը!
|