More Like this

1. Proximity Gaps for Reed–Solomon Codes

   https://doi.org/10.1145/3614423  

   Ben-Sasson, Eli ; Carmon, Dan ; Ishai, Yuval ; Kopparty, Swastik ; Saraf, Shubhangi ( August 2023 , Journal of the ACM)

   A collection of sets displays aproximity gapwith respect to some property if for every set in the collection, either (i) all members areδ-close to the property in relative Hamming distance or (ii) only a tiny fraction of members areδ-close to the property. In particular, no set in the collection has roughly half of its membersδ-close to the property and the othersδ-far from it.

   We show that the collection of affine spaces displays a proximity gap with respect to Reed–Solomon (RS) codes, even over small fields, of size polynomial in the dimension of the code, and the gap applies to anyδsmaller than the Johnson/Guruswami–Sudan list-decoding bound of the RS code. We also show near-optimal gap results, over fields of (at least)linearsize in the RS code dimension, forδsmaller than the unique decoding radius. Concretely, ifδis smaller than half the minimal distance of an RS code\(V\subset {\mathbb {F}}_q^n \), every affine space is either entirelyδ-close to the code, or alternatively at most an (n/q)-fraction of it isδ-close to the code. Finally, we discuss several applications of our proximity gap results to distributed storage, multi-party cryptographic protocols, and concretely efficient proof systems.

   We prove the proximity gap results by analyzing the execution of classical algebraic decoding algorithms for Reed–Solomon codes (due to Berlekamp–Welch and Guruswami–Sudan) on aformal elementof an affine space. This involves working with Reed–Solomon codes whose base field is an (infinite) rational function field. Our proofs are obtained by developing an extension (to function fields) of a strategy of Arora and Sudan for analyzing low-degree tests.

    

   more » « less
2. Pseudorandom Linear Codes Are List-Decodable to Capacity

   Putterman, Aaron ; Pyne, Edward ( January 2024 , 15th Innovations in Theoretical Computer Science Conference, ITCS 2024)

   We introduce a novel family of expander-based error correcting codes. These codes can be sampled with randomness linear in the block-length, and achieve list decoding capacity (among other local properties). Our expander-based codes can be made starting from any family of sufficiently low-bias codes, and as a consequence, we give the first construction of a family of algebraic codes that can be sampled with linear randomness and achieve list-decoding capacity. We achieve this by introducing the notion of a pseudorandom puncturing of a code, where we select n indices of a base code C ⊂ 𝔽_q^m in a correlated fashion. Concretely, whereas a random linear code (i.e. a truly random puncturing of the Hadamard code) requires O(n log(m)) random bits to sample, we sample a pseudorandom linear code with O(n + log (m)) random bits by instantiating our pseudorandom puncturing as a length n random walk on an exapnder graph on [m]. In particular, we extend a result of Guruswami and Mosheiff (FOCS 2022) and show that a pseudorandom puncturing of a small-bias code satisfies the same local properties as a random linear code with high probability. As a further application of our techniques, we also show that pseudorandom puncturings of Reed-Solomon codes are list-recoverable beyond the Johnson bound, extending a result of Lund and Potukuchi (RANDOM 2020). We do this by instead analyzing properties of codes with large distance, and show that pseudorandom puncturings still work well in this regime. 

   more » « less
3. NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem

   https://doi.org/10.1109/FOCS.2016.86  

   Gandikota, Venkata ; Ghazi, Badih ; Grigorescu, Elena ( October 2016 , FOCS)

   Establishing the complexity of {\em Bounded Distance Decoding} for Reed-Solomon codes is a fundamental open problem in coding theory, explicitly asked by Guruswami and Vardy (IEEE Trans. Inf. Theory, 2005). The problem is motivated by the large current gap between the regime when it is NP-hard, and the regime when it is efficiently solvable (i.e., the Johnson radius). We show the first NP-hardness results for asymptotically smaller decoding radii than the maximum likelihood decoding radius of Guruswami and Vardy. Specifically, for Reed-Solomon codes of length $N$ and dimension $K=O(N)$, we show that it is NP-hard to decode more than $ N-K- c\frac{\log N}{\log\log N}$ errors (with $c>0$ an absolute constant). Moreover, we show that the problem is NP-hard under quasipolynomial-time reductions for an error amount $> N-K- c\log{N}$ (with $c>0$ an absolute constant). An alternative natural reformulation of the Bounded Distance Decoding problem for Reed-Solomon codes is as a {\em Polynomial Reconstruction} problem. In this view, our results show that it is NP-hard to decide whether there exists a degree $K$ polynomial passing through $K+ c\frac{\log N}{\log\log N}$ points from a given set of points $(a_1, b_1), (a_2, b_2)\ldots, (a_N, b_N)$. Furthermore, it is NP-hard under quasipolynomial-time reductions to decide whether there is a degree $K$ polynomial passing through $K+c\log{N}$ many points. These results follow from the NP-hardness of a generalization of the classical Subset Sum problem to higher moments, called {\em Moments Subset Sum}, which has been a known open problem, and which may be of independent interest. We further reveal a strong connection with the well-studied Prouhet-Tarry-Escott problem in Number Theory, which turns out to capture a main barrier in extending our techniques. We believe the Prouhet-Tarry-Escott problem deserves further study in the theoretical computer science community. 

   more » « less
4. Scaled Fast Nested Key Equation Solver for Generalized Integrated Interleaved BCH Decoders

   https://doi.org/10.1109/ICASSP39728.2021.9414846  

   Xie, Zhenshan ; Zhang, Xinmiao ( June 2021 , IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP))

   The generalized integrated interleaved BCH (GII-BCH) codes are among the best error-correcting codes for next-generation terabit/s memories. The key equation solver (KES) in the nested decoding of GII codes limits the achievable clock frequency. Recently, by polynomial scalar pre-computation, the critical path of the nested KES for Reed-Solomon (RS)-based GII codes has been reduced to one multiplier. However, for GII-BCH codes, the nested KES has more complicated formulas in order to skip the odd iterations and hence prior techniques do not directly extend. This paper proposes novel reformulations of the nested BCH KES to enable scalar pre-computation. Additionally, polynomial scaling is incorporated to enable complexity reduction. As a result, the critical path of the nested BCH KES with odd iterations skipped is reduced to one multiplier. For an example GII-BCH code over GF(2^{12}), the proposed design reduces the average nested BCH KES latency to around a half with similar silicon area compared to the best prior design. 

   more » « less
5. Lifted Multiplicity Codes and the Disjoint Repair Property

   https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.38  

   Li, Ray ; Wootters, Mary ( October 2019 , Leibniz international proceedings in informatics)

   Lifted Reed Solomon Codes (Guo, Kopparty, Sudan 2013) were introduced in the context of locally correctable and testable codes. They are multivariate polynomials whose restriction to any line is a codeword of a Reed-Solomon code. We consider a generalization of their construction, which we call lifted multiplicity codes. These are multivariate polynomial codes whose restriction to any line is a codeword of a multiplicity code (Kopparty, Saraf, Yekhanin 2014). We show that lifted multiplicity codes have a better trade-off between redundancy and a notion of locality called the t-disjoint-repair-group property than previously known constructions. More precisely, we show that, for t <=sqrt{N}, lifted multiplicity codes with length N and redundancy O(t^{0.585} sqrt{N}) have the property that any symbol of a codeword can be reconstructed in t different ways, each using a disjoint subset of the other coordinates. This gives the best known trade-off for this problem for any super-constant t < sqrt{N}. We also give an alternative analysis of lifted Reed Solomon codes using dual codes, which may be of independent interest. 

   more » « less