More Like this

1. Ideal-Theoretic Explanation of Capacity-Achieving Decoding

   https://doi.org/10.1109/TIT.2023.3345890  

   Bhandari, Siddharth; Harsha, Prahladh; Kumar, Mrinal; Sudan, Madhu (February 2024, IEEE Transactions on Information Theory)

   In this work, we present an abstract framework for some algebraic error-correcting codes with the aim of capturing codes that are list-decodable to capacity, along with their decoding algorithms. In the polynomial ideal framework, a code is specified by some ideals in a polynomial ring, messages are polynomials and the encoding of a message polynomial is the collection of residues of that polynomial modulo the ideals. We present an alternate way of viewing this class of codes in terms of linear operators, and show that this alternate view makes their algorithmic list-decodability amenable to analysis. Our framework leads to a new class of codes that we call affine Folded Reed-Solomon codes (which are themselves a special case of the broader class we explore). These codes are common generalizations of the well-studied Folded Reed-Solomon codes and Univariate Multiplicity codes as well as the less-studied Additive Folded Reed-Solomon codes, and lead to a large family of codes that were not previously known/studied. More significantly our framework also captures the algorithmic list-decodability of the constituent codes. Specifically, we present a unified view of the decoding algorithm for ideal-theoretic codes and show that the decodability reduces to the analysis of the distance of some related codes. We show that a good bound on this distance leads to a capacity-achieving performance of the underlying code, providing a unifying explanation of known capacity-achieving results. In the specific case of affine Folded Reed-Solomon codes, our framework shows that they are efficiently list-decodable up to capacity (for appropriate setting of the parameters), thereby unifying the previous results for Folded Reed-Solomon, Multiplicity and Additive Folded Reed-Solomon codes. 

   more » « less
2. 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
3. RASSS: A perfidy-aware protocol for designing trustworthy distributed systems

   https://doi.org/10.1109/DFT.2017.8244432  

   Bu, Lake; Nguyen, Hien D.; Kinsy, Michel A. (October 2017, 2017 IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems (DFT))

   Robust Adaptive Secure Secret Sharing (RASSS) is a protocol for reconstructing secrets and information in distributed computing systems even in the presence of a large number of untrusted participants. Since the original Shamir's Secret Sharing scheme, there have been efforts to secure the technique against dishonest shareholders. Early on, researchers determined that the Reed-Solomon encoding property of the Shamir's share distribution equation and its decoding algorithm could tolerate cheaters up to one third of the total shareholders. However, if the number of cheaters grows beyond the error correcting capability (distance) of the Reed-Solomon codes, the reconstruction of the secret is hindered. Untrusted participants or cheaters could hide in the decoding procedure, or even frame up the honest parties. In this paper, we solve this challenge and propose a secure protocol that is no longer constrained by the limitations of the Reed-Solomon codes. As long as there are a minimum number of honest shareholders, the RASSS protocol is able to identify the cheaters and retrieve the correct secret or information in a distributed system with a probability close to 1 with less than 60% of hardware overhead. Furthermore, the adaptive nature of the protocol enables considerable hardware and timing resource savings and makes RASSS highly practical. 

   more » « less
4. Proximity Gaps for Reed–Solomon Codes

   https://doi.org/10.1109/FOCS46700.2020.00088  

   Ben-Sasson, Eli; Carmon, Dan; Ishai, Yuval; Kopparty, Swastik; Saraf, Shubhangi (November 2020, 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2020))

   null (Ed.)

   A collection of sets displays a proximity gap with 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) linear size 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 ⊂ Fq 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 a formal element of 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
5. 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