Pith. sign in

REVIEW 2 major objections 4 minor 65 references

Explicit Codes approaching Generalized Singleton Bound using Expanders

T0 review · 2 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Expander-based codes attain the ε-relaxed generalized Singleton bound with constant alphabet and optimal list size.

desk verdict A genuinely new expander-based route to list-decoding capacity; the main local-to-global theorem is sound, but Corollary 3.7 has a real parameter mismatch that needs fixing. read the letter →

arxiv 2502.07308 v1 pith:KA4A6PN5 submitted 2025-02-11 cs.IT cs.CCmath.IT

Fernando Granha Jeronimo , Tushant Mittal , Shashank Srivastava , Madhur Tulsiani This is my paper · ORCID
classification cs.ITcs.CCmath.IT MSC 94B6594B3505C48
keywords listdecodinggeneralizedSingletonboundexpandercodesAELconstructionaverage-radiusLDPCsum-of-squaresexplicit
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that a single expander-based device—the Alon–Edmonds–Luby (AEL) distance amplification procedure—can transform any high-rate code into a code that meets the ε-relaxed generalized Singleton bound, not just the classical distance bound. Concretely, for every rate R, every ε>0, and every list size k, the paper constructs explicit codes over a constant alphabet with the property that for any received word g and any list H of at most k codewords, the average Hamming distance from g to the list is at least ((|H|-1)/|H|)(1−R−ε). Such codes can be list decoded up to radius (k−1)/k(1−R−ε) deterministically in time $n^{{O_{k,ε}}$(1)}. The proof is combinatorial and spectral, using expansion and a partition/erasure analysis of local projections instead of polynomial interpolation. As a corollary the paper obtains explicit LDPC codes achieving list decoding capacity.

What carries the argument

The carrying object is the AEL construction: an (n,d,λ)-expander bipartite graph G, a constant-sized inner code Cin ⊆ Σ^d_in, and a high-rate outer code Cout; the codeword of Cout is written on the left vertices, spread across edges, and grouped again on right vertices. The proof mechanism is a local-to-global amplification for the stronger property of being average-radius list decodable with erasures. At each left vertex, the local projections of the k codewords induce a partition of the list; the expander mixing lemma guarantees a nontrivial partition τ on a δout n / k^k fraction of left vertices. The local average-distance inequality for Cin is applied to the parts of τ, while error locations common to all members of a part are treated as erasures and handled by induction on k, which converts the local inequalities into the global inequality. The decoding algorithm then replicates this proof inside a degree-t sum-of-squares relaxation, where pseudocodewords replace integral codewords and η-goodness controls pseudocovariance, yielding the generalized Singleton bound for the relaxation.

What would settle it

Take any explicit code from the construction and search all received words g (or a sufficiently large random sample) for a list of k codewords whose average Hamming distance is below ((k−1)/k)(1−ρ−ε); the main theorem predicts that no such configuration exists, so any one would refute the claim.

Watch

Extended reading notes

Core claim

The central claim is a local-to-global theorem: if the constant-sized inner code Cin used in the AEL construction is (δ0, k, ε/2) average-radius list decodable with erasures, and the bipartite expander has second eigenvalue λ ≤ δout/(6 k^k) ε, then the resulting AEL code is (δ0, k, ε) average-radius list decodable with erasures. The paper instantiates this with inner codes given by random linear codes (or, if full explicitness is required, folded Reed–Solomon codes) and with high-rate outer codes, producing for every ρ, ε, k an explicit family of rate ≥ρ codes over an alphabet of size $2^{{(k^k/ε)^{O(1)}}$} satisfying the ε-relaxed generalized Singleton bound. The same round of ideas is carried through a sum-of-squares relaxation, yielding a deterministic algorithm that list decodes up to radius (k−1)/k(1−ρ−ε) with a list of size at most k−1.

Load-bearing premise

The conclusion is conditional on the existence of a constant-sized inner code that is (1−ρ, k, ε/2) average-radius list decodable with erasures at essentially the target distance; if no such code exists with the stated alphabet, rate, and slack, the claimed final parameters must be weakened to match the inner code actually available.

Editorial extensions

If this is right

  • For any fixed list size k, the bound forces every ball of radius (k−1)/k(1−R−ε) to contain at most k−1 codewords; choosing k=O(1/ε) gives list size O(1/ε) at list-decoding capacity.
  • The construction yields explicit LDPC codes—codes given by parity checks of size 2^{(1/ε)^{O(1)}}—that achieve list decoding capacity, which were previously known only through random constructions.
  • No polynomial interpolation or algebraic geometry is used: the entire list-size bound follows from expansion and the partition/erasure argument, so any high-rate outer code with constant distance, e.g. LDPC or Tanner codes, can be amplified.
  • The decoding algorithm runs in deterministic time n^{2^{O(k^{4k}/ε^{10})}}, with the list size at most k−1, for any received word and any radius up to (k−1)/k(1−R−ε).

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial extension: the same 'common-error-locations become erasures' mechanism should transfer to interleaved codes and other graph products, where the complete bipartite graph case (λ=0) is already noted in the paper; one test is whether it yields list-recovery bounds for tensor products of arbitrary codes.
  • Editorial extension: the sum-of-squares proof shows the generalized Singleton bound is certified by a convex relaxation, not only by integral combinatorics; this suggests other spectral decoding bounds, such as Johnson-type radii, might be relaxed the same way.
  • Editorial extension: since the outer code only needs high rate, constant distance, and unique decodability, the construction may compose with any near-MDS or expander-based outer family, potentially giving linear-time encodable and decodable capacity-approaching codes with different tradeoffs.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper presents an expander-based construction of explicit codes approaching the relaxed generalized Singleton bound. The main combinatorial result (Theorem 3.2) shows that the Alon–Edmonds–Luby (AEL) distance amplification preserves a strong form of average-radius list decodability with erasures: if a constant-sized inner code is (δ0, k, ε/2) average-radius list decodable with erasures and the expander has sufficiently small second eigenvalue, then the AEL code is (δ0, k, ε) average-radius list decodable with erasures. The proof uses a partition of the list induced by local projections and an induction with erasures. The authors instantiate the inner code via random linear codes or folded Reed-Solomon codes, obtaining a family of codes with rate at least ρ, constant alphabet size, and list decoding up to radius (k−1)/k(1−ρ−ε). They also provide an SoS-based list decoding algorithm for these codes and observe that the construction inherits the LDPC property from the outer code.

Significance. The conceptual contribution is significant: it provides a non-algebraic, purely combinatorial route to capacity-approaching list decodable codes, and the AEL-based local-to-global argument is elegant and largely self-contained. If the parameter issues identified below are repaired, the result would give the first explicit LDPC codes achieving list decoding capacity, with an optimal O(1/ε) list size, and a new proof technique based on expander mixing and erasure-based induction rather than polynomial interpolation. The algorithmic extension via SoS is also a valuable contribution, though it relies on the same parameter instantiations. The main proof of Theorem 3.2 appears sound; the problems lie in the parameter matching when instantiating the theorem with known inner codes.

major comments (2)
  1. [Corollary 3.7 and Theorem 1.1] The instantiation of the inner code has a parameter mismatch. Corollary 4.3 guarantees that a random linear code of rate r is (1−r, L, ε) average-radius list decodable with erasures. The proof of Corollary 3.7 chooses r = ρ+ε/4 and then claims the inner code is (1−ρ, k, ε/2). This is inconsistent: the correct property is (1−ρ−ε/4, k, ε/2). Applying Theorem 3.2 with δ0 = 1−ρ−ε/4 yields an AEL code that is (1−ρ−ε/4, k, ε), so the final inequality becomes ∑_h Δ(g,h) ≥ (|H|−1)(1−ρ−5ε/4), not the claimed (|H|−1)(1−ρ−ε). To obtain the stated bound, the inner code rate should be ρin = ρ+ε (in the nontrivial regime ε < 1−ρ). Additionally, the choice ρin = ρ+ε/4 requires ρ+ε/4 ≤ 1, i.e., ε ≤ 4(1−ρ); for larger ε the proof needs a separate vacuous case, since the target bound is then non-positive. This mismatch affects Corollary 3.7, the informal Theorem 1.1, and Corollary 5.25.
  2. [Corollary 4.3] The union bound over subsets S is miscalculated. The displayed bound states 2^n κ ≤ 2^n · 2^{(10L/ε+1)·εn/2} · q^{−⌊εn/2⌋} ≥ 1 − 2^{-n/3} for q ≥ 2^{2/ε}·2^{10L/ε}. Substituting this q gives q^{−εn/2} = 2^{−(2+10L)n/2}, and the total exponent becomes n + (5L + ε/2)n − (1+5L)n = εn/2. Hence the bound is 2^{εn/2}, which grows with n and cannot be ≤ 2^{-n/3}. The argument can be repaired by taking a larger alphabet (roughly q ≥ 2^{(10L + 10/3)/ε}) or by a sharper count of subsets of size at most (1−ρ)n, but as written the proof does not establish the claimed probability bound. Since the existence of suitable inner codes is not in question, this is a repairable quantitative error, but it is load-bearing for the explicit construction via random linear codes.
minor comments (4)
  1. [Claim 4.1] The hypothesis of Claim 4.1 says that each punctured code CS is (1−ρ, L, ε/(1−s)) average-radius list decodable, but the proof uses the condition with 1−ρ(CS). Since ρ(CS) ≥ ρ, the stated hypothesis is stronger than what is verified in Corollary 4.3. The proof should be aligned with the statement.
  2. [Corollary 3.7 (rate inequality)] The inequality (1−ε/4)(ρ+ε/4) ≥ ρ is asserted without qualification, but it holds only when ε ≤ 4(1−ρ). In the interesting regime where 1−ρ−ε > 0, this condition is automatically satisfied, so the claim is correct there, but the proof should mention the case split for ε ≥ 1−ρ.
  3. [Corollary 3.7 (explicitness)] The phrase 'explicit inner codes' is used for codes obtained by searching over all linear codes of a constant length and rate. This is a standard convention for constant-sized objects, but it should be stated explicitly, since the inner code is not given by a deterministic formula. The alternative fully explicit choice via folded Reed-Solomon codes is mentioned but not used in the main corollary.
  4. [Throughout] There are several typos that should be fixed: 'probablity' in the proof of Corollary 4.3; 'psueocodewords' in Definition 5.9; 'diffcult' in the discussion of distances in Section 5.1; and 'captuted' in the Introduction.

Circularity Check

0 steps flagged · score 2.0 of 10

No circularity: AEL local-to-global theorem is an independent reduction; self-citations are framework-only and not load-bearing.

full rationale

The derivation chain is a reduction, not a tautology. Theorem 3.2 proves that if a constant-sized inner code C_in is (δ0, k, ε/2) average-radius list decodable with erasures, then the AEL-amplified code C_AEL is (δ0, k, ε) with erasures. The proof is an induction using the expander mixing lemma (Claim 3.5, Lemma 3.6) and never assumes the conclusion for C_AEL; it only uses the inner-code property on local projections. The inner codes are supplied externally: Corollary 4.3 derives the erasure version from [AGL24b, Thm. 1.3] via a puncturing argument, and Corollary 4.6 derives it from [CZ24, Thm. 1.3]; neither citation is to the present authors and neither presupposes the AEL result. The SoS algorithm (Section 5) is adapted from [JST23], but the generalized-Singleton SoS inequality is proved in Section 5.2 (Theorem 5.18) rather than imported as a black box, and Appendix A generalizes standard pseudocovariance arguments. Citations to [Sri24] are pointers for related interleaving discussion, not load-bearing. The parameter mismatch in Corollary 3.7 (`ρ_in = ρ + ε/4` yields δ0 = 1 − ρ − ε/4 instead of 1 − ρ) is a numerical accounting error that weakens the stated bound; this is a correctness issue, not circularity, because the erroneous step does not identify the target result with an input. No equation or cited theorem is equivalent to its own input by construction.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper's contribution is a reduction theorem, so the non-reduced ingredients (inner code existence, expander graphs, outer codes, SoS machinery) are imported from prior literature. No data fitting occurs; all parameters are explicit functions of ε and k.

assumptions (6)
  • standard math Expander mixing lemma for (n,d,λ)-expanders
    Used throughout the proof of Theorem 3.2 and in the SoS lemmas to bound local-to-global averages.
  • standard math Existence of explicit (n,d,λ)-expander families with λ ≤ 2√(d-1)/d
    Invoked in Corollary 3.7 to choose d large enough so λ meets the required bound. Based on LPS double covers.
  • domain assumption Random linear codes are average-radius list decodable with erasures ([AGL24b])
    Used to construct the inner code Cin with the required property in Corollary 4.3.
  • domain assumption Folded Reed-Solomon codes are average-radius list decodable ([CZ24])
    Alternative explicit inner code via Corollary 4.6.
  • domain assumption Explicit high-rate Tanner codes with constant distance and linear-time unique decoding ([GRS23], [Zém01])
    Used as the outer code Cout in the AEL construction.
  • standard math SoS hierarchy and pseudocovariance machinery from [JST23]
    The algorithmic proof relies on SoS relaxations, η-good pseudocodewords, and conditioning lemmas adapted from [JST23].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Explicit Codes approaching Generalized Singleton Bound using Expanders." pith.science (2026). https://pith.science/paper/KA4A6PN5

@misc{pith2026250207308,
  author       = {Pith},
  title        = {Pith review of: Explicit Codes approaching Generalized Singleton Bound using Expanders},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KA4A6PN5}},
  note         = {Machine review of arXiv:2502.07308}
}
abstract

We construct a new family of explicit codes that are list decodable to capacity and achieve an optimal list size of $O(\frac{1}{\epsilon})$. In contrast to existing explicit constructions of codes achieving list decoding capacity, our arguments do not rely on algebraic structure but utilize simple combinatorial properties of expander graphs. Our construction is based on a celebrated distance amplification procedure due to Alon, Edmonds, and Luby [FOCS'95], which transforms any high-rate code into one with near-optimal rate-distance tradeoff. We generalize it to show that the same procedure can be used to transform any high-rate code into one that achieves list decoding capacity. Our proof can be interpreted as a "local-to-global" phenomenon for (a slight strengthening of) the generalized Singleton bound. Using this construction, for every $R, \epsilon \in (0,1)$ and $k \in \mathbb{N}^+$, we obtain an \emph{explicit} family of codes $\mathcal{C} \subseteq \Sigma^n$, with rate $R$ such that, - They achieve the $\epsilon$-relaxed generalized Singleton bound: for any $g \in \Sigma^n$ and any list $\mathcal{H}$ of at most $k$ codewords, we have, \[ \underset{h \in \mathcal{H}}{\mathbb{E}} [\Delta(g,h)] ~\geq~ \frac{|\mathcal{H}|-1}{|\mathcal{H}|} \cdot (1 - R - \epsilon). \] - The alphabet size is a constant depending only on $\epsilon$ and $k$. - They can be list decoded up to radius $\frac{k-1}{k}(1-R-\epsilon)$, in time $n^{O_{k,\epsilon}(1)}$. As a corollary of our result, we also obtain the first explicit construction of LDPC codes achieving list decoding capacity, and in fact arbitrarily close to the generalized Singleton bound.

Figures

Figures reproduced from arXiv: 2502.07308 by the authors.

Figure 1
Figure 1. Illustration of the AEL procedure 3 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Local projections and partitions Induction. The above idea of using erasures for common error locations, can also be extended to arbitrary partitions τ ∗ = (H1, . . . , Hp). We now apply the local distance inequalities for codewords f1,ℓ , . . . , fp,ℓ corresponding to the different parts, at a “good” vertex ℓ ∈ L ∗ where the sampling bound holds. This gives ∑ j∈[p] ∆(gℓ , f j,ℓ ) ≥ (p − 1) · (δ0 − ε) ⇒ ∑ j∈[p] sj ≥… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

65 extracted references · 51 canonical work pages

  1. [1]

    N. Alon, J. Bruck, J. Naor, M. Naor, and R. Roth. Construction of asymptotically good, low-rate error-correcting codes through pseudo-random graphs. IEEE Transactions on Information Theory , 28:509--516, 1992

    1992

  2. [2]

    N. Alon, J. Edmonds, and M. Luby. Linear time erasure codes with nearly optimal recovery. In Proceedings of IEEE 36th Annual Foundations of Computer Science , pages 512--519, 1995. https://doi.org/10.1109/SFCS.1995.492581 doi:10.1109/SFCS.1995.492581

    arXiv 1995

  3. [3]

    AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets

    Omar Alrabiah, Venkatesan Guruswami, and Ray Li. AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1367--1378, 2024. URL: https://epubs.siam.org/doi/abs/10.1137/1.9781611977912.55, https://arxiv.org/a...

    work page Pith review arXiv 2024

  4. [4]

    Random Reed-Solomon Codes Achieve List-Decoding Capacity With Linear-Sized Alphabets

    Omar Alrabiah, Venkatesan Guruswami, and Ray Li. Randomly Punctured Reed–Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields . In Proceedings of the 56th ACM Symposium on Theory of Computing , 2024. https://arxiv.org/abs/2304.09445 arXiv:2304.09445 , https://doi.org/10.1145/3618260.3649634 doi:10.1145/3618260.3649634

    work page Pith review arXiv 2024

  5. [5]

    List decoding of direct sum codes

    Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, and Madhur Tulsiani. List decoding of direct sum codes. In Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms , pages 1412--1425. SIAM, 2020

    2020

  6. [6]

    Improved field size bounds for higher order mds codes

    Joshua Brakensiek, Manik Dhar, and Sivakanth Gopi. Improved field size bounds for higher order mds codes. IEEE Transactions on Information Theory , 70(10):6950--6960, 2024. https://doi.org/10.1109/TIT.2024.3449030 doi:10.1109/TIT.2024.3449030

    work page arXiv 2024

  7. [7]

    Approaching the Quantum Singleton Bound with Approximate Error Correction

    Thiago Bergamaschi, Louis Golowich, and Sam Gunn. A pproaching the Quantum Singleton Bound with Approximate Error Correction . In Proceedings of the 56th ACM Symposium on Theory of Computing , page 1507–1516, 2024. https://arxiv.org/abs/2212.09935 arXiv:2212.09935 , https://doi.org/10.1145/3618260.3649680 doi:10.1145/3618260.3649680

    work page Pith review arXiv 2024

  8. [8]

    Generic Reed-Solomon Codes Achieve List-decoding Capacity

    Joshua Brakensiek, Sivakanth Gopi, and Visu Makam. Generic Reed-Solomon Codes Achieve List-Decoding Capacity . In Proceedings of the 55th ACM Symposium on Theory of Computing , page 1488–1501, 2023. https://arxiv.org/abs/2206.05256 arXiv:2206.05256 , https://doi.org/10.1145/3564246.3585128 doi:10.1145/3564246.3585128

    work page Pith review arXiv 2023

Show all 65 references
  1. [9]

    Ideal-Theoretic Explanation of Capacity-Achieving Decoding

    Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, and Madhu Sudan. Ideal-Theoretic Explanation of Capacity-Achieving Decoding . IEEE Trans. Inf. Theor. , 70(2):1107–1123, dec 2023. https://doi.org/10.1109/TIT.2023.3345890 doi:10.1109/TIT.2023.3345890

    2023

  2. [10]

    Rounding semidefinite programming hierarchies via global correlation

    Boaz Barak, Prasad Raghavendra, and David Steurer. Rounding semidefinite programming hierarchies via global correlation. In Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science , pages 472--481, 2011

    2011

  3. [11]

    Sum-of-squares proofs and the quest toward optimal algorithms

    Boaz Barak and David Steurer. Sum-of-squares proofs and the quest toward optimal algorithms. arXiv preprint arXiv:1404.5236 , 2014. URL: https://arxiv.org/abs/1404.5236

    2014 arXiv

  4. [12]

    Explicit subcodes of R eed- S olomon codes that efficiently achieve list decoding capacity, 2024

    Amit Berman, Yaron Shany, and Itzhak Tamo. Explicit subcodes of R eed- S olomon codes that efficiently achieve list decoding capacity, 2024. URL: https://arxiv.org/abs/2401.15034, https://arxiv.org/abs/2401.15034 arXiv:2401.15034

    2024 arXiv

  5. [13]

    Reconstructing curves in three (and higher) dimensional space from noisy data

    Don Coppersmith and Madhu Sudan. Reconstructing curves in three (and higher) dimensional space from noisy data. In Proceedings of the 35th ACM Symposium on Theory of Computing , page 136–142, 2003. https://doi.org/10.1145/780542.780563 doi:10.1145/780542.780563

    2003

  6. [14]

    Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds , 2024

    Yeyuan Chen and Zihan Zhang. Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds , 2024. https://arxiv.org/abs/2408.15925 arXiv:2408.15925

    2024 arXiv

  7. [15]

    Subspace evasive sets

    Zeev Dvir and Shachar Lovett. Subspace evasive sets. In Proceedings of the 44th ACM Symposium on Theory of Computing , pages 351--358, New York, NY, USA, 2012. Association for Computing Machinery. https://doi.org/10.1145/2213977.2214010 doi:10.1145/2213977.2214010

    2012

  8. [16]

    List decoding for noisy channels

    Peter Elias. List decoding for noisy channels. Technical Report 335, Research Laboratory of Electronics, MIT, 1957

    1957

  9. [17]

    Semialgebraic proofs and efficient algorithm design

    Noah Fleming, Pravesh Kothari, and Toniann Pitassi. Semialgebraic proofs and efficient algorithm design. Foundations and Trends® in Theoretical Computer Science , 14(1-2):1--221, 2019. URL: http://dx.doi.org/10.1561/0400000086, https://doi.org/10.1561/0400000086 doi:10.1561/0400000086

    2019 doi

  10. [18]

    List-decodability with large radius for Reed-Solomon codes

    Asaf Ferber, Matthew Kwan, and Lisa Sauermann. List-decodability with large radius for Reed-Solomon codes . In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 720--726, Los Alamitos, CA, USA, February 2022. IEEE Computer Society. https://doi.o...

    2021

  11. [20]

    On the list-decodability of random linear codes

    Venkatesan Guruswami, Johan Håstad, and Swastik Kopparty. On the list-decodability of random linear codes. IEEE Transactions on Information Theory , 57(2):718--725, 2011. https://doi.org/10.1109/TIT.2010.2095170 doi:10.1109/TIT.2010.2095170

    2011

  12. [21]

    Guruswami and P

    V. Guruswami and P. Indyk . Linear-time encodable/decodable codes with near-optimal rate. IEEE Transactions on Information Theory , 51(10):3393--3400, 2005

    2005

  13. [22]

    Explicit subspace designs

    Venkatesan Guruswami and Swastik Kopparty. Explicit subspace designs. Combinatorica , 36(2):161--185, April 2016. https://doi.org/10.1007/s00493-014-3169-1 doi:10.1007/s00493-014-3169-1

    2016 doi

  14. [23]

    Locally testable and locally correctable codes approaching the Gilbert - Varshamov bound

    Sivakanth Gopi, Swastik Kopparty, Rafael Oliveira, Noga Ron-Zewi, and Shubhangi Saraf. Locally testable and locally correctable codes approaching the Gilbert - Varshamov bound. In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms , SODA '17, pages 2073--2091, 2017

    2017

  15. [24]

    Improved list-decodability and list-recoverability of R eed– S olomon codes via tree packings

    Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, and Mary Wootters. Improved list-decodability and list-recoverability of R eed– S olomon codes via tree packings. SIAM Journal on Computing , 53(2):389--430, 2024. https://arxiv.org/abs/2011.04453 arXiv:2011.04453 , https://doi.o...

    2024 arXiv

  16. [25]

    Combinatorial Limitations of Average-Radius List-Decoding

    Venkatesan Guruswami and Srivatsan Narayanan. Combinatorial Limitations of Average-Radius List-Decoding . IEEE Transactions on Information Theory , 60(10):5827--5842, 2014. https://doi.org/10.1109/TIT.2014.2343224 doi:10.1109/TIT.2014.2343224

    2014

  17. [26]

    Explicit capacity-achieving list-decodable codes

    Venkatesan Guruswami and Atri Rudra. Explicit capacity-achieving list-decodable codes. In Proceedings of the 38th ACM Symposium on Theory of Computing , pages 1--10, 2006

    2006

  18. [27]

    Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy

    Venkatesan Guruswami and Atri Rudra. Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Transactions on Information Theory , 54(1):135--150, 2008. https://doi.org/10.1109/TIT.2007.911222 doi:10.1109/TIT.2007.911222

    2008

  19. [28]

    Essential coding theory

    Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Essential coding theory. Available at https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/, 2023

    2023

  20. [29]

    Efficient list-decoding with constant alphabet and list sizes

    Zeyu Guo and Noga Ron-Zewi. Efficient list-decoding with constant alphabet and list sizes. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , STOC 2021, page 1502–1515, New York, NY, USA, 2021. Association for Computing Machinery. https://doi.org/1...

    2021

  21. [30]

    Goldreich and M

    O. Goldreich and M. Sudan. Computational indistinguishibility: k samples versus k+1 samples. In Proceedings of the 13th IEEE Conference on Computational Complexity , 1998

    1998

  22. [31]

    List-decoding and list-recovery of Reed–Solomon codes beyond the Johnson radius for every rate

    Eitan Goldberg, Chong Shangguan, and Itzhak Tamo. List-decoding and list-recovery of Reed–Solomon codes beyond the Johnson radius for every rate. IEEE Transactions on Information Theory , 69(4):2261--2268, 2023. https://doi.org/10.1109/TIT.2022.3222877 doi:10.1109/TIT.2022.3222877

    2023

  23. [32]

    Algorithmic results in list decoding

    Venkatesan Guruswami. Algorithmic results in list decoding. Foundations and Trends in Theoretical Computer Science , 2(2), 2006

    2006

  24. [33]

    Artin automorphisms, cyclotomic function fields, and folded list-decodable codes

    Venkatesan Guruswami. Artin automorphisms, cyclotomic function fields, and folded list-decodable codes. In Proceedings of the 41st ACM Symposium on Theory of Computing , 2009. https://doi.org/10.1145/1536414.1536420 doi:10.1145/1536414.1536420

    2009

  25. [34]

    Linear-algebraic list decoding of folded Reed-Solomon codes

    Venkatesan Guruswami. Linear-algebraic list decoding of folded Reed-Solomon codes. In Proceedings of the 26th IEEE Conference on Computational Complexity , 2011

    2011

  26. [35]

    Unbalanced expanders and randomness extractors from P arvaresh-- V ardy codes

    Venkatesan Guruswami, Christopher Umans, and Salil Vadhan. Unbalanced expanders and randomness extractors from P arvaresh-- V ardy codes. Journal of the ACM , 2009

    2009

  27. [36]

    Linear-Algebraic List Decoding for Variants of Reed--Solomon Codes

    Venkatesan Guruswami and Carol Wang. Linear-Algebraic List Decoding for Variants of Reed--Solomon Codes . IEEE Transactions on Information Theory , 59(6):3257--3268, 2013. https://doi.org/10.1109/TIT.2013.2246813 doi:10.1109/TIT.2013.2246813

    2013

  28. [37]

    List Decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin Subcodes up to the Singleton Bound

    Venkatesan Guruswami and Chaoping Xing. List Decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin Subcodes up to the Singleton Bound . In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing , STOC '13, page 843–852, New York, NY, USA, 2013. Associat...

    2013

  29. [38]

    Optimal rate list decoding over bounded alphabets using algebraic-geometric codes

    Venkatesan Guruswami and Chaoping Xing. Optimal rate list decoding over bounded alphabets using algebraic-geometric codes. J. ACM , 69(2), Jan 2022. https://doi.org/10.1145/3506668 doi:10.1145/3506668

    2022 doi

  30. [40]

    Linear-time list recovery of high-rate expander codes

    Brett Hemenway and Mary Wootters. Linear-time list recovery of high-rate expander codes. Information and Computation , 261:202--218, 2018. ICALP 2015. https://doi.org/10.1016/j.ic.2018.02.004 doi:10.1016/j.ic.2018.02.004

    2018 doi

  31. [41]

    Unique decoding of explicit -balanced codes near the G ilbert-- V arshamov bound

    Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, and Madhur Tulsiani. Unique decoding of explicit -balanced codes near the G ilbert-- V arshamov bound. In Proceedings of the 61st IEEE Symposium on Foundations of Computer Science , 2020

    2020

  32. [42]

    List decoding of Tanner and expander amplified codes from distance certificates

    Fernando Granha Jeronimo, Shashank Srivastava, and Madhur Tulsiani. List decoding of Tanner and expander amplified codes from distance certificates. In Proceedings of the 64th IEEE Symposium on Foundations of Computer Science , 2023. https://arxiv.org/abs/2311.02263 arXiv:2311.02263

    2023 arXiv

  33. [43]

    High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity

    Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf. High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity. In Proceedings of the 48th ACM Symposium on Theory of Computing , page 202–215, 2016. https://doi.org/10.1145/2897518.2...

    2016

  34. [44]

    List-Decoding Multiplicity Codes

    Swastik Kopparty. List-Decoding Multiplicity Codes . Theory of Computing , 11(5):149--182, 2015. https://doi.org/10.4086/toc.2015.v011a005 doi:10.4086/toc.2015.v011a005

    2015 doi

  35. [45]

    Improved Decoding of Folded Reed-Solomon and Multiplicity Codes

    Swastik Kopparty, Noga Ron - Zewi, Shubhangi Saraf, and Mary Wootters. Improved Decoding of Folded Reed-Solomon and Multiplicity Codes . In Mikkel Thorup, editor, Proceedings of the 59th IEEE Symposium on Foundations of Computer Science , 2018. https://arxiv.org/abs/1805.01498...

    2018 arXiv

  36. [46]

    Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes

    Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, and Mary Wootters. Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes . SIAM Journal on Computing , 52(3):794--840, 2023. https://doi.org/10.1137/20M1370215 doi:10.1137/20M1370215

    2023 doi

  37. [47]

    High-rate codes with sublinear-time decoding

    Swastik Kopparty, Shubhangi Saraf, and Sergey Yekhanin. High-rate codes with sublinear-time decoding. J. ACM , 61(5), September 2014. https://doi.org/10.1145/2629416 doi:10.1145/2629416

    2014 doi

  38. [48]

    Phillips, and Peter Sarnak

    Alexander Lubotzky, R. Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica , 8:261--277, 1988

    1988

  39. [49]

    Mosheiff, N

    J. Mosheiff, N. Resch, N. Ron-Zewi, S. Silas, and M. Wootters. LDPC codes achieve list decoding capacity. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 458--469, Los Alamitos, CA, USA, nov 2020. IEEE Computer Society. https://doi.org/10.1...

    2020

  40. [50]

    SOS Is Not Obviously Automatizable, Even Approximately

    Ryan O'Donnell. SOS Is Not Obviously Automatizable, Even Approximately . In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) , volume 67 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 59:1--59:10, D...

    2017 doi

  41. [51]

    Correcting errors beyond the G uruswami- S udan radius in polynomial time

    Farzad Parvaresh and Alexander Vardy. Correcting errors beyond the G uruswami- S udan radius in polynomial time. In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science , pages 285--294, 2005

    2005

  42. [52]

    Ron M. Roth. Higher-Order MDS Codes . IEEE Transactions on Information Theory , 68(12):7798--7816, 2022. https://doi.org/10.1109/TIT.2022.3194521 doi:10.1109/TIT.2022.3194521

    2022

  43. [53]

    Richelson and S

    S. Richelson and S. Roy. Gilbert and V arshamov meet J ohnson: List-decoding explicit nearly-optimal binary codes. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 194--205, Los Alamitos, CA, USA, nov 2023. IEEE Computer Society. https://doi...

    2023

  44. [54]

    Reed and G

    I.S. Reed and G. Solomon. Polynomial codes over certain finite fields. Journal of SIAM , 8:300--304, 1960

    1960

  45. [55]

    Every list-decodable code for high noise has abundant near-optimal rate puncturings

    Atri Rudra and Mary Wootters. Every list-decodable code for high noise has abundant near-optimal rate puncturings. In Proceedings of the 46th ACM Symposium on Theory of Computing , pages 764--773, 2014. https://doi.org/10.1145/2591796.2591797 doi:10.1145/2591796.2591797

    2014

  46. [56]

    On the bit complexity of sum-of-squares proofs

    Prasad Raghavendra and Benjamin Weitz. On the bit complexity of sum-of-squares proofs. In Proceedings of the 44th International Colloquium on Automata, Languages and Programming . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017

    2017

  47. [57]

    Continuous Optimization for Decoding Errors

    Shashank Srivastava. Continuous Optimization for Decoding Errors . PhD thesis, Toyota Technlogical Institute at Chicago (TTIC), 2024. https://arxiv.org/abs/2408.14652 arXiv:2408.14652

    2024 arXiv

  48. [58]

    Improved list size for folded Reed - Solomon codes

    Shashank Srivastava. Improved list size for folded Reed - Solomon codes. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2040--2050, 2025. https://arxiv.org/abs/2410.09031 arXiv:2410.09031 , https://doi.org/10.1137/1.9781611978322.64 ...

    2025 arXiv

  49. [59]

    Combinatorial list-decoding of Reed - Solomon codes beyond the Johnson radius

    Chong Shangguan and Itzhak Tamo. Combinatorial list-decoding of Reed - Solomon codes beyond the Johnson radius. In Proceedings of the 52nd ACM Symposium on Theory of Computing , page 538–551, 2020. https://doi.org/10.1145/3357713.3384295 doi:10.1145/3357713.3384295

    2020

  50. [60]

    Decoding of Reed - Solomon codes beyond the error-correction bound

    Madhu Sudan. Decoding of Reed - Solomon codes beyond the error-correction bound. Journal of Complexity , 13(1):180--193, 1997

    1997

  51. [61]

    List decoding: algorithms and applications

    Madhu Sudan. List decoding: algorithms and applications. SIGACT News , 31(1):16--27, 2000

    2000

  52. [62]

    Tighter list-size bounds for list-decoding and recovery of folded Reed-Solomon and multiplicity codes

    Itzhak Tamo. Tighter list-size bounds for list-decoding and recovery of folded Reed-Solomon and multiplicity codes. IEEE Transactions on Information Theory , 2024. https://doi.org/10.1109/TIT.2024.3402171 doi:10.1109/TIT.2024.3402171

    2024

  53. [63]

    Some Applications of Coding Theory in Computational Complexity

    Luca Trevisan. Some Applications of Coding Theory in Computational Complexity . Quaderni di Matematica , 13:347--424, 2004. https://arxiv.org/abs/cs.CC/0409044 arXiv:cs.CC/0409044

    2004

  54. [64]

    Salil P. Vadhan. Pseudorandomness . Now Publishers Inc., 2012

    2012

  55. [65]

    On the list decodability of random linear codes with large error rates

    Mary Wootters. On the list decodability of random linear codes with large error rates. In Proceedings of the 45th ACM Symposium on Theory of Computing , pages 853--860, 2013. https://arxiv.org/abs/1302.2261 arXiv:1302.2261 , https://doi.org/10.1145/2488608.2488716 doi:10.1145/...

    2013 arXiv

  56. [66]

    J. M. Wozencraft. List decoding. Technical report, Quarterly Progress Report, Research Laboratory of Electronics, MIT , 1958

    1958

  57. [67]

    Z \'e mor

    G. Z \'e mor. On expander codes. IEEE Transactions on Information Theory , 47(2):835--837, 2001. https://doi.org/10.1109/18.910593 doi:10.1109/18.910593

    2001 doi

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.