Many hash-based proof systems check that committed words are close to Reed-Solomon codewords by testing one random combination of them. Their soundness analysis uses a proximity gap: if the combination agrees with a codeword on many positions, so do the original words, on the same positions, except for a few ... more >>>

Suppose there is an oracle $\mathcal{O}$ that computes a tiny fraction of the entries of the product of two uniformly random binary matrices over integers. We prove that there is a nearly linear-size randomized $\mathcal{O}$-oracle circuit that, with high probability, computes all the entries of the product of every pair ... more >>>

For a linear code $C\subseteq\mathbb{F}_q^n$, we say that $C$ satisfies the \emph{proximity-gaps property} up to distance $\delta_1$ if, for every $\delta_2>\delta_1$ and every $f,g\in\mathbb{F}_q^n$, at least one of which is $\delta_2$-far from $C$ in relative Hamming distance, there are only a small fraction (typically at most $\operatorname{poly}(n)/q$) of \emph{exceptional coefficients} ... more >>>