Summary: Algebraic proof systems reduce computational problems to problems about estimating the distance of a sequence of functions \(\vec{u}=(u_1,\dots, 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,\dots,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=\mathsf{span}(u_1,\dots,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 \(\frac{1}{2}\delta\)-far from \(V\) [G. N. Rothblum et al., in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. New York, NY: Association for Computing Machinery (ACM). 793–802 (2013; Zbl 1293.68250)].
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 A. Polishchuk and D. A. Spielman [in: Proceedings of the 26th annual ACM symposium on theory of computing, STOC ’94, Montreal, Canada, May 23–25, 1994. New York, NY: Association for Computing Machinery (ACM). 194–203 (1994; Zbl 1345.68180)] 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 A. Chiesa et al. [“On axis-parallel tests for tensor product codes”, LIPIcs – Leibniz Int. Proc. Inform. 81, Article 39, 22 p. (2017; doi:10.4230/LIPIcs.APPROX-RANDOM.2017.39)] 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 E. Ben-Sasson et al. [“Fast Reed-Solomon interactive oracle proofs of proximity”, LIPIcs – Leibniz Int. Proc. Inform. 107, Article 14, 17 p. (2018; doi:10.4230/LIPIcs.ICALP.2018.14)] and extend it to the “list-decoding” regime, bringing it closer to the Johnson bound.
For the entire collection see [Zbl 1390.68026].