Authors
Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf
Publication date
2018
Conference
33rd Computational Complexity Conference (CCC 2018)
Publisher
Schloss-Dagstuhl-Leibniz Zentrum für Informatik
Description
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 worst-case to average-case 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 delta-far from (all elements) of V in relative Hamming distance, then nearly all elements of U are (1-epsilon) delta-far 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 state-of-the-art which showed that nearly all elements of U are 1/2delta-far from V [Rothblum, Vadhan and Wigderson, STOC 2013]. When V is a Reed-Solomon (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 affine-invariance 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 (1-epsilon)-far from V; as above, epsilon depends only on the distance of V and approaches 0 as the distance of V …
Total citations
2019202020212022202356388
Scholar articles
E Ben-Sasson, S Kopparty, S Saraf - 33rd Computational Complexity Conference (CCC …, 2018