Reed-Solomon (RS) codes were recently shown to exhibit an intriguing proximity gap phenomenon. Specifically, given a collection of strings with some algebraic structure (such as belonging to a line or affine space), either all of them are δ-close to RS codewords, or most of them are δ-far from the code. Here δ is the proximity parameter which can be taken to be the Johnson radius 1−√R of the RS code (R being the code rate), matching its best known list-decodability. Proximity gaps play a crucial role in the soundness analysis of Interactive Oracle Proof (IOP) protocols used in Succinct Non-Interactive Arguments of Knowledge (SNARKs) and the resulting proof sizes.

We show that if a language $\mathcal{L}$ admits a public-coin unambiguous interactive proof (UIP) with round complexity $\ell$, where a bits are communicated per round, then the batch language ${\mathcal{L}}^{\otimes k}$, i.e. the set of k-tuples of statements all belonging to $\mathcal{L}$, has an unambiguous interactive proof with round complexity $\ell \cdot$ polylog $(k)$, per-round communication of $a \cdot \ell \cdot$ polylog $(k)+$ poly $(\ell)$ bits, assuming the verifier in the UIP has depth bounded by polylog $(k)$. Prior to this work, the best known batch UIP for ${\mathcal{L}}^{\otimes k}$ required communication complexity at least ($\operatorname{poly}(a) \cdot k^{\epsilon}+k$) $\cdot \ell^{1 / \epsilon}$ for any arbitrarily small constant $\epsilon\gt 0$ (Reingold-Rothblum-Rothblum, STOC 2016). As a corollary of our result, we obtain a doubly efficient proof system, that is, a proof system whose proving overhead is polynomial in the time of the underlying computation, for any language computable in polynomial space and in time at most $n^{O\left(\sqrt{\frac{\log n}{\log \log n}}\right)}$. This expands the state of the art of doubly efficient proof systems: prior to our work, such systems were known for languages computable in polynomial space and in time $n^{(\log n)^{\delta}}$ for a small $\delta\gt 0$ significantly smaller than 1/2 (Reingold-Rothblum-Rothblum, STOC 2016).

We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon (FRS) codes can be made to run in$\tilde{O}(n)$time. Univariate multiplicity codes and FRS codes are natural variants of Reed-Solomon codes that were discovered and studied for their applications to list decoding. It is known that for every$\varepsilon > 0$, and rate$r\in(0,1)$, there exist explicit families of these codes that have rate$r$and can be list decoded from a$(1-r-\varepsilon)$fraction of errors with constant list size in polynomial time (Guruswami & Wang (IEEE Trans. Inform. Theory 2013) and Kopparty, Ron-Zewi, Saraf & Wootters (SIAM J. Comput. 2023)). In this work, we present randomized algorithms that perform the above list-decoding tasks in$\tilde{O}(n)$, where$n$is the block-length of the code. Our algorithms have two main components. The first component builds upon the lattice-based approach of Alekhnovich (IEEE Trans. Inf. Theory 2005), who designed a$\tilde{O}(n)$time list-decoding algorithm for Reed-Solomon codes approaching the Johnson radius. As part of the second component, we design$\tilde{O}(n)$time algorithms for two natural algebraic problems: given a$(m+2)$-variate polynomial$Q(x, y_{0}, \ldots, y_{m})=\tilde{Q}(x)+\sum\nolimits_{i=0}^{m} Q_{i}(x) \cdot y_{i}$the first algorithm solves order-m linear differential equations of the form$Q\left(x, f(x), \frac{d f}{d x}, \ldots, \frac{d^{m} f}{d x^{m}}\right) \equiv 0$while the second solves functional equations of the form$Q(x, f(x), f(\gamma x), \ldots, f(\gamma^{m}x))\equiv 0$, where$m$is an arbitrary constant and$\gamma$is a field element of sufficiently high order. These algorithms can be viewed as generalizations of classical$\tilde{O}(n)$time algorithms of Sieveking (Computing 1972) and Kung (Numer. Math. 1974) for computing the modular inverse of a power series, and might be of independent interest.