BenSasson, Eli ;
Kopparty, Swastik ;
Saraf, Shubhangi
WorstCase to Average Case Reductions for the Distance to a Code
Abstract
Algebraic proof systems reduce computational problems to problems about estimating the distance of a sequence of functions vec{u}=(u_1,..., u_k), given as oracles, from a linear error correcting code V. The soundness of such systems relies on methods that act "locally" on vec{u} and map it to a single function u^* that is, roughly, as far from V as are u_1,..., u_k.
Motivated by these applications to efficient proof systems, we study a natural worstcase to averagecase reduction of distance for linear spaces, and show several general cases in which the following statement holds: If some member of a linear space U=span(u_1,...,u_k) is deltafar from (all elements) of V in relative Hamming distance, then nearly all elements of U are (1epsilon)deltafar from V; the value of epsilon depends only on the distance of the code V and approaches 0 as that distance approaches 1. Our results improve on the previous stateoftheart which showed that nearly all elements of U are 1/2deltafar from V [Rothblum, Vadhan and Wigderson, STOC 2013].
When V is a ReedSolomon (RS) code, as is often the case for algebraic proof systems, we show how to boost distance via a new "local" transformation that may be useful elsewhere. Relying on the affineinvariance of V, we map a vector u to a random linear combination of affine transformations of u, and show this process amplifies distance from V. Assuming V is an RS code with sufficiently large distance, this amplification process converts a function u that is somewhat far from V to one that is (1epsilon)far from V; as above, epsilon depends only on the distance of V and approaches 0 as the distance of V approaches 1.
We give two concrete application of these techniques. First, we revisit the axisparallel lowdegree test for bivariate polynomials of [PolischukSpielman, STOC 1994] and prove a "listdecoding" type result for it, when the degree of one axis is extremely small. This result is similar to the recent listdecodingregime result of [Chiesa, Manohar and Shinkar, RANDOM 2017] but is proved using different techniques, and allows the degree in one axis to be arbitrarily large. Second, we improve the soundness analysis of the recent RS proximity testing protocol of [BenSasson et al., ICALP 2018] and extend it to the "listdecoding" regime, bringing it closer to the Johnson bound.
BibTeX  Entry
@InProceedings{bensasson_et_al:LIPIcs:2018:8865,
author = {Eli BenSasson and Swastik Kopparty and Shubhangi Saraf},
title = {{WorstCase to Average Case Reductions for the Distance to a Code}},
booktitle = {33rd Computational Complexity Conference (CCC 2018)},
pages = {24:124:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770699},
ISSN = {18688969},
year = {2018},
volume = {102},
editor = {Rocco A. Servedio},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2018/8865},
URN = {urn:nbn:de:0030drops88654},
doi = {10.4230/LIPIcs.CCC.2018.24},
annote = {Keywords: Proximity testing, ReedSolomon codes, algebraic coding complexity}
}
04.06.2018
Keywords: 

Proximity testing, ReedSolomon codes, algebraic coding complexity 
Seminar: 

33rd Computational Complexity Conference (CCC 2018)

Issue date: 

2018 
Date of publication: 

04.06.2018 