Worst-Case 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 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 approaches 1.
We give two concrete application of these techniques. First, we revisit the axis-parallel low-degree test for bivariate polynomials of [Polischuk-Spielman, STOC 1994] and prove a "list-decoding" type result for it, when the degree of one axis is extremely small. This result is similar to the recent list-decoding-regime 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 [Ben-Sasson et al., ICALP 2018] and extend it to the "list-decoding" regime, bringing it closer to the Johnson bound.