Name
Abstract | ||
|---|---|---|
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
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup>
, 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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1109/FOCS46700.2020.00088 | 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | Volume |
Concrete Efficiency, Interactive Oracle Proof, Low degree testing, Reed Solomon codes | Conference | 2020 |
ISSN | ISBN | Citations |
1523-8288 | 978-1-7281-9622-0 | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eli Ben-Sasson | 1 | 1641 | 86.98 |
| Dan Carmon | 2 | 0 | 0.34 |
| Yuval Ishai | 3 | 4364 | 246.22 |
| Swastik Kopparty | 4 | 384 | 32.89 |
| Shubhangi Saraf | 5 | 263 | 24.55 |