A generator is a function that maps a random seed to a list of coefficients. We study generators that preserve distance to a linear code: the linear combination of any list of vectors using coefficients sampled by the generator has distance to the code no smaller than that of the original vectors, except for a small error. Distance preservation plays a central role in modern probabilistic proofs, and has been formalized in several ways. We study mutual correlated agreement, the strongest known form of distance preservation. We initiate a systematic study of mutual correlated agreement, aiming to characterize the class of generators with this property. Towards this, we study polynomial generators, a rich class that includes all examples of generators considered in the distance preservation literature. Our main result is that all polynomial generators guarantee mutual correlated agreement for every linear code. This improves on prior work both in generality (the class of generators covered) and in parameters (the error bounds). We additionally provide new results for the case where the linear code is a Reed-Solomon code, which is of particular interest in applications. We prove that all polynomial generators satisfy mutual correlated agreement for Reed-Solomon codes up to the Johnson bound. In particular, we improve upon the state-of-the-art by Ben-Sasson, Carmon, Ishai, Kopparty, and Saraf (FOCS 2020) and answer a question posed by Arnon, Chiesa, Fenzi, and Yogev (Eurocrypt 2025). Along the way we develop a flexible and general toolbox for mutual correlated agreement, and are the first to establish distance preservation for generators that lie beyond polynomial generators.

Aaronson (STOC 2010) conjectured that almost k-wise independence fools constant-depth circuits; he called this the generalised Linial-Nisan conjecture. Aaronson himself later found a counterexample for depth-3 circuits. We give here an improved counterexample for depth-2 circuits (DNFs). This shows, for instance, that Bazzi’s celebrated result (k-wise independence fools DNFs) cannot be generalised in a natural way. We also propose a way to circumvent our counterexample: We define a new notion of pseudorandomness called local couplings and show that it fools DNFs and even decision lists.

This paper gives a nearly tight characterization of the quantum communication complexity of permutation-invariant Boolean functions. With such a characterization, we show that the quantum and randomized communication complexity of permutation-invariant Boolean functions are quadratically equivalent (up to a polylogarithmic factor of the input size). Our results extend a recent line of research regarding query complexity to communication complexity, showing symmetry prevents exponential quantum speedups. Furthermore, we show that the Log-rank Conjecture holds for any non-trivial total permutation-invariant Boolean function. Moreover, we establish a relationship between the quantum/classical communication complexity and the approximate rank of permutation-invariant Boolean functions. This implies the correctness of the Log-approximate-rank Conjecture for permutation-invariant Boolean functions in both randomized and quantum settings (up to a polylogarithmic factor of the input size).

What is the Σ32-circuit complexity (depth 3, bottom-fanin 2) of the 2n-bit inner product function? The complexity is known to be exponential 2αnn for some αn=Ω(1). We show that the limiting constant α≔limsupαn satisfies0.847...≤α≤0.965.... Determining α is one of the seemingly-simplest open problems about depth-3 circuits. The question was recently raised by Golovnev, Kulikov, and Williams (ITCS 2021) and Frankl, Gryaznov, and Talebanfard (ITCS 2022), who observed that α∈[0.5,1]. To obtain our improved bounds, we analyse a covering LP that captures the Σ32-complexity up to polynomial factors. In particular, our lower bound is proved by constructing a feasible solution to the dual LP.