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.

Rossman [In $\textit{Proc. $34$th Comput. Complexity Conf.}$, 2019] introduced the notion of $\textit{criticality}$. The criticality of a Boolean function $f : \{0,1\}^n \to \{0,1\}$ is the minimum $λ\geq 1$ such that for all positive integers $t$, \[ \Pr_{ρ\sim \mathcal{R}_p}\left[\text{DT}_{\text{depth}}(f|_ρ) \geq t\right] \leq (pλ)^t. \] Hästad's celebrated switching lemma shows that the criticality of any $k$-DNF is at most $O(k)$. Subsequent improvements to correlation bounds of $\text{AC}^0$-circuits against parity showed that the criticality of any $\text{AC}^0$-$\textit{circuit}$ of size $S$ and depth $d+1$ is at most $O(\log S)^d$ and any $\textit{regular}$ $\text{AC}^0$-$\textit{formula}$ of size $S$ and depth $d+1$ is at most $O\left(\frac1d \cdot \log S\right)^d$. We strengthen these results by showing that the criticality of $\textit{any}$ $\text{AC}^0$-formula (not necessarily regular) of size $S$ and depth $d+1$ is at most $O\left(\frac1d\cdot {\log S}\right)^d$, resolving a conjecture due to Rossman. This result also implies Rossman's optimal lower bound on the size of any depth-$d$ $\text{AC}^0$-formula computing parity [$\textit{Comput. Complexity, 27(2):209--223, 2018.}$]. Our result implies tight correlation bounds against parity, tight Fourier concentration results and improved $\#$SAT algorithm for $\text{AC}^0$-formulae.

The multiplicity Schwartz-Zippel lemma asserts that over a field, a low-degree polynomial cannot vanish with high multiplicity very often on a sufficiently large product set. Since its discovery in a work of Dvir, Kopparty, Saraf and Sudan [DKSS13], the lemma has found numerous applications in both math and computer science; in particular, in the definition and properties of multiplicity codes by Kopparty, Saraf and Yekhanin [KSY14]. In this work, we show how to algorithmize the multiplicity Schwartz-Zippel lemma for arbitrary product sets over any field. In other words, we give an efficient algorithm for unique decoding of multivariate multiplicity codes from half their minimum distance on arbitrary product sets over all fields. Previously, such an algorithm was known either when the underlying product set had a nice algebraic structure (for instance, was a subfield) [Kop15] or when the underlying field had large (or zero) characteristic, the multiplicity parameter was sufficiently large and the multiplicity code had distance bounded away from 1 [BHKS21b]. In particular, even unique decoding of bivariate multiplicity codes with multiplicity two from half their minimum distance was not known over arbitrary product sets over any field. Our algorithm builds upon a result of Kim & Kopparty [KK17] who gave an algorithmic version of the Schwartz-Zippel lemma (without multiplicities) or equivalently, an efficient algorithm for unique decoding of Reed-Muller codes over arbitrary product sets. We introduce a refined notion of distance based on the multiplicity Schwartz-Zippel lemma and design a unique decoding algorithm for this distance measure. On the way, we give an alternate analysis of Forney's classical generalized minimum distance decoder that might be of independent interest. * The full version of the paper which includes the missing proofs can be accessed at [BHKS21a]. Research of the first, second and fourth authors supported by the Department of Atomic Energy, Government of India, under project 12-R&D-TFR-5.01-0500. This work was done while the first author was at TIFR, where he was supported in part by the Google PhD Fellowship and at the Simons Institute for the Theory of Computing where he was supported by the Simons-Berkeley Postdoctoral Fellowship. Research of the second author supported in part by the Swarnajayanti Fellowship.