Advances in the Theory of Error-Correcting Codes
2024-04-08..2024-04-12
Berkeley, United States
who it's for
coding theorists, theoretical computer scientists, information theorists, algebraic geometers, cryptographers, communications engineers
topics
list decoding of expander codes; Johnson bound list decoding; Lasserre SDP rounding; SOS pseudo-distributions; locally decodable codes for deletions; interactive feedback error correction; Hermitian trace codes; dual of evaluation codes; multiplication property codes; LDPC on triangle complexes; fast list-decoding Reed-Solomon variants; relaxed locally correctable codes (RLCCs)
| title | author | length |
|---|---|---|
| List Decoding of Tanner and Expander Amplified Codes... | Shashank Srivastava | 48m |
Polynomial-time list decoder up to the Johnson bound for Tanner/expander codes with inner distance delta0 and graph spectral gap lambda, achieving decoding up… | ||
| Gilbert and Varshamov meet Johnson: List Decoding Nearly-Optimal Binary Codes | Silas Richelson | 39m |
Gives an explicit algorithm that list-decodes Ta‑Shma’s near–Gilbert–Varshamov binary code to the Johnson bound, proving recovery from a (1−ρ)/2 error fraction… | ||
| Binary Error Correcting Codes with Minimal Noiseless Feedback | Rachel Zhang | 35m |
Presents optimal limited-feedback binary codes: constructs feedback codes (errors and erasures) that reach 1/3 adversarial error resilience using only O(log k)… | ||
| What Can and What Cannot Be Done by LP and SDP (An Incomplete Overview) | Alexander Barg | 51m |
Gives a calculation-free proof of MRRW by projecting Krawtchouk polynomials to a degree-k space, forming a tridiagonal (Jacobi) operator and bounding its… | ||
| The Hermitian Trace Code | Amnon Ta-Shma | 53m |
Proves a concrete bound: for any non-square low‑degree function f in the Hermitian function field (degree d odd) the quadratic character sum over the p^3… | ||
| Constant Query Local Decoding Against Deletions Is Impossible | Meghal Gupta | 41m |
Proves that constant‑query locally decodable codes for insertions and deletions do not exist: a reduction of Blocki et al. plus an information‑theoretic… | ||
| Binary Codes with Resilience Beyond 1/4 via Interaction | Klim Efremenko | 40m |
Constructs two-way binary codes that achieve resilience strictly >1/4 at constant rate with Bob sending one short reply, using a three-round non-adaptive… | ||
| Signal, if you can’t (for the damage) | Ran Gelles | 47m |
Claim: arbitrary noiseless protocols are simulatable by pure signaling when every link’s content is destroyed, provided the network is 2-edge connected… | ||
| Dual of (evaluation) codes | Hiram Lopez | 41m |
Gives an explicit algebraic recipe: the dual of an evaluation code uses the same evaluation points, complementary monomials coming from the footprint (compute… | ||
| Codes with the multiplication property | Irit Dveer Dinur | 46m |
Constructs LDPC codes on a triangle complex built from coset-style groups over F_p[t]/(irreducible of degree n), embedding each triangle as a point in F_p^{9n}… | ||
| Coding Theory in Almost Linear Time and Sublinear Space | Dana Moshkovitz | 44m |
Constructs asymptotically good codes that achieve deterministic encoding or deterministic decoding in n^{1+o(1)} time while using sublinear space, splitting… | ||
| Relaxed Local Correctability from Local Testing | Vinayak Kumar, Geoffrey Mon | 37m |
Constructs the first asymptotically good relaxed locally correctable codes that use polylogarithmic queries to recover a target bit or output failure, closing… | ||
| Asymptotically-Good RLCCs with (log n)^{2+o(1)} Queries | Tal Yankovitz | 42m |
Constructs asymptotically good RLCCs with (log n)^{2+o(1)} queries by replacing full LTCs in the Kumar Mon reduction with vanilla expander codes that satisfy… | ||
| Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes | Prahladh Harsha | 52m |
Shows explicit codes (univariate multiplicity and folded Reed–Solomon) that are list-decodable up to capacity and whose decoding runs in n·polylog n time… | ||
| An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes | Peter Manohar | 45m |
Proves that any linear 3‑query LCC C:{0,1}^k→{0,1}^n must have blocklength n ≥ exp(k^{1/8}), giving the first separation between q‑query LCCs and LDCs; shows… | ||
| Tree codes | Gil Cohen | 46m |
Open problem for 30+ years: construct a constant alphabet tree code with constant relative distance δ>0 and poly(n) time per edge (strongly explicit). Known… | ||
| List-decoding random codes ensembles | Ray Li | 46m |
Random linear codes over F2 are shown to match random (nonlinear) codes: rate 1−H(p)−ε is list-decodable to radius p with list size roughly Θ(H(p)/ε) and that… | ||
| Parameterized Inapproximability of the Minimum Distance Problem over all Fields... | Venkatesan Guruswami | 48m |
Proves the Minimum Distance Problem parameterized by the distance bound is W[1]-hard under randomized reductions over every fixed finite field, with no FPT… | ||
| Higher Order MDS Codes | Sivakanth Gopi | 49m |
Main claim: choosing Reed‑Solomon evaluation points at random over a large field yields codes that meet the list‑decoding Singleton bound, i.e., generic… | ||
| Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles | Omar Alrabiah | 43m |
Proves that any binary linear 3-query LCC of block length n has dimension k ≤ O_δ(log^2 n · log log n), nearly matching quadratic Reed–Muller (Θ(log^2 n))… | ||
| nothing matches | ||