 Award ID(s):
 1649515
 NSFPAR ID:
 10033549
 Date Published:
 Journal Name:
 FOCS
 Page Range / eLocation ID:
 760 to 769
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

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 ReedSolomon (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/GuruswamiSudan listdecoding bound of the RS code. We also show nearoptimal 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, multiparty cryptographic protocols, and concretely efficient proof systems. We prove the proximity gap results by analyzing the execution of classical algebraic decoding algorithms for ReedSolomon codes (due to BerlekampWelch and GuruswamiSudan) on a formal element of an affine space. This involves working with ReedSolomon 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 lowdegree tests.more » « less

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 listdecoding bound of the RS code. We also show nearoptimal 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 , every affine space is either entirely\(V\subset {\mathbb {F}}_q^n \) δ 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, multiparty 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 lowdegree tests. 
We introduce a novel family of expanderbased error correcting codes. These codes can be sampled with randomness linear in the blocklength, and achieve list decoding capacity (among other local properties). Our expanderbased codes can be made starting from any family of sufficiently lowbias 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 listdecoding 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 smallbias 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 ReedSolomon codes are listrecoverable 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

Ahn, HeeKap ; Sadakane, Kunihiko (Ed.)In the standard planar kcenter clustering problem, one is given a set P of n points in the plane, and the goal is to select k center points, so as to minimize the maximum distance over points in P to their nearest center. Here we initiate the systematic study of the clustering with neighborhoods problem, which generalizes the kcenter problem to allow the covered objects to be a set of general disjoint convex objects C rather than just a point set P. For this problem we first show that there is a PTAS for approximating the number of centers. Specifically, if r_opt is the optimal radius for k centers, then in n^O(1/ε²) time we can produce a set of (1+ε)k centers with radius ≤ r_opt. If instead one considers the standard goal of approximating the optimal clustering radius, while keeping k as a hard constraint, we show that the radius cannot be approximated within any factor in polynomial time unless P = NP, even when C is a set of line segments. When C is a set of unit disks we show the problem is hard to approximate within a factor of (√{13}√3)(2√3) ≈ 6.99. This hardness result complements our main result, where we show that when the objects are disks, of possibly differing radii, there is a (5+2√3)≈ 8.46 approximation algorithm. Additionally, for unit disks we give an O(n log k)+(k/ε)^O(k) time (1+ε)approximation to the optimal radius, that is, an FPTAS for constant k whose running time depends only linearly on n. Finally, we show that the one dimensional version of the problem, even when intersections are allowed, can be solved exactly in O(n log n) time.more » « less

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 ReedSolomon 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 tradeoff between redundancy and a notion of locality called the tdisjointrepairgroup 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 tradeoff for this problem for any superconstant 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