Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR

Jarosław Błasiok, Paul Lou, Alon Rosen, Madhu Sudan · 2026

Read Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR by Jarosław Błasiok, Paul Lou, Alon Rosen, Madhu Sudan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-04188.txt.

Introduction

Jarosław Błasiok and team disproved conjectures linking expansion to hardness for noisy k-XOR. Lower bounds in restricted models like Sum-of-Squares had suggested that expanding graphs make the problem hard. The authors built an explicit family of near-optimal expanders for which noisy k-XOR runs in polynomial time. Their graphs rest on the lossless expanders of Guruswami, Umans, and Vadhan, reinterpreted so the XOR problem becomes decoding Reed-Muller codes from random errors.

Catalog record

CREATORJarosław Błasiok, Paul Lou, Alon Rosen, Madhu Sudan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE59194
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.04188

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR Jarosław Błasiok, Paul Lou, Alon Rosen, Madhu Sudan Abstract In the noisy k k -XOR problem, one is given y ∈ 𝔽 2 M y\in\mathbb{F}_{2}^{M} and must distinguish between y y uniform and y = A ​ x + e y=Ax+e , where A A is the adjacency matrix of a k k -left-regular bipartite graph with N N variables and M M constraints, x ∈ 𝔽 2 N x\in\mathbb{F}_{2}^{N} is random, and e e is noise with rate η \eta . Lower bounds in restricted computational models such as Sum-of-Squares and low-degree polynomials are closely tied to the expansion of A A , leading to conjectures that expansion implies hardness. We show that such conjectures are false by constructing an explicit family of graphs with near-optimal expansion for which noisy k k -XOR is solvable in polynomial time. Our construction combines two powerful directions of work in pseudorandomness and coding theory that have not been previously put together. Specifically, our graphs are based on the lossless expanders of Guruswami, Umans and Vadhan (JACM 2009). Our key insight is that by an appropriate interpretation of the vertices of their graphs, the noisy XOR problem turns into the problem of decoding Reed-Muller codes from random errors. Then we build on a powerful body of work from the 2010s correcting from large amounts of random errors. Putting these together yields our construction. Concretely, we obtain explicit families for which noisy k k -XOR is polynomial-time solvable at constant noise rate η = 1 / 3 \eta=1/3 for graphs with M = 2 O ⁡ ( log 2 ⁡ N ) M=2^{O(\log^{2}N)} , k = ( log ⁡ N ) O ⁡ ( 1 ) k=(\log N)^{O(1)} , and ( N 1 − α , 1 − o ⁡ ( 1 ) ) (N^{1-\alpha},1-o(1)) -expansion. Under standard conjectures on Reed-Muller codes over the binary erasure channel, this extends to families with M = N O ⁡ ( 1 ) M=N^{O(1)} , k = ( log ⁡ N ) O ⁡ ( 1 ) k=(\log N)^{O(1)} , expansion ( N 1 − α , 1 − o ⁡ ( 1 ) ) (N^{1-\alpha},1-o(1)) and polynomial-time algorithms at noise rate η = N − c \eta=N^{-c} . 1 Introduction Noisy k -XOR is a canonical hypothesis-testing problem for sparse random linear systems and a central example in the study of statistical-computational gaps. A widely held intuition attributes such gaps to expansion properties of an associated graph. We show that this intuition fails in general by providing an explicit counterexample. This serves as a cautionary tale: near-optimal expansion does not, by itself, imply hardness for noisy k -XOR. While many prior works focus on the case of constant k , for example k=3 , our results apply when k is polylogarithmic in the number of variables. We are not aware of any compelling reason to expect this regime to be algorithmically easier than the constant- k setting. 1.1 The Noisy k -XOR Problem Given a vector y\in\mathbb{F}_{2}^{M} , one must distinguish between y being sampled from the null distribution where y is uniform random and the planted distribution where y=A_{H}\cdot x+e that we now describe. In the planted distribution, we consider matrices A_{H}\in\mathbb{F}_{2}^{M\times N} where every row is of Hamming weight k , a uniform random x\in\mathbb{F}_{2}^{N} , and a sparse noise vector e\in\mathbb{F}_{2}^{M} . Viewing A_{H} as the adjacency matrix of a k -left regular bipartite graph H where each of the M rows corresponds to a constraint and each of the N columns corresponds to a variable, we have the following definition. Definition 1 (Noisy k-XOR Distinguishing Problem) . In the \eta -noisy XOR distinguishing problem associated with a constraint graph H , we are given a vector y\in\mathbb{F}_{2}^{M} , with a promise that either • (Null case): y\sim\mathrm{Unif}(\mathbb{F}_{2}^{M}) , • (Planted case): y=A_{H}\cdot x+e , where x\in\mathbb{F}_{2}^{N} is a uniform random vector, and each element of the noise vector e\in\mathbb{F}_{2}^{M} is independently 1 with probability \eta (and 0 otherwise). The goal of the algorithm is to distinguish between those two distributions. For example, an algorithm \mathcal{A} is said to succeed in the distinguishing task, if \left|\Pr_{y\sim\mathrm{Unif}{\mathbb{F}_{2}^{M}}}[\mathcal{A}(y)=1]-\Pr_{\begin{subarray}{c}x\sim\mathbb{F}_{2}^{N}\\ e\sim\mathsf{Ber}(\eta)^{M}\end{subarray}}[\mathcal{A}(A_{H}\cdot x+e)=1]\right|>1/10. When M\leq N , the planted and the null distributions are typically identical (as long as the adjacency matrix A_{H} is of full rank), so the problem is not well-posed. We therefore only consider the setting where M>N . In this setting, the columns of the matrix A_{H} span a linear code in \mathbb{F}_{2}^{M} , and the problem is essentially equivalent to deciding whether y is a randomly corrupted codeword (through a binary symmetric channel with noise level \eta ), or a random word from \mathbb{F}_{2}^{M} . 1.2 Statistical-Computational Gap and Expansion Properties When H is a random dense graph, or equivalently when A_{H} is a random linear code, the problem is the classical Learning Parity with Noise (LPN) problem, which is conjectured to remain subexponentially hard even with subexponentially many samples [ 15 , 4 ] . In the sparse regime, a large body of work has studied random k -left-regular constraint graphs H . This includes hardness and cryptographic formulations of sparse noisy parity/ k -LIN/XOR-code problems [ 4 , 19 , 18 ] , as well as algorithmic work on planted and random CSPs [ 25 , 14 ] . The sparse regime is believed to exhibit a statistical-computational gap: the problem becomes polynomial-time solvable beyond a known computational threshold, but is conjectured to remain hard below it. Some of this line of work was motivated by Feige’s reduction from refuting random k -SAT to refuting random k -XOR [ 24 , 23 ] . Closely related, though somewhat orthogonal to the noisy k -XOR distinguishing problem itself, is a line of work on local pseudorandom generators, Goldreich-type functions, and algebraic attacks, often instantiated using sparse random or expanding graphs [ 43 , 17 , 7 , 8 , 9 ] . Positive results in this setting provide a polynomial-time algorithm when M\gtrsim N^{k/2} . For these values of parameters, the polynomial-time distinguisher between planted and null distributions is trivial (the birthday paradox implies that with decent probability there are two equations on exactly the same set of variables, and one can just check if those two have the same value), and a non-trivial algorithm can either recover a planted solution, or refute a random instance [ 22 , 11 , 5 , 46 , 30 ] . Moreover, some evidence for computational hardness is provided by the means of lower bounds in the restricted models of computation (Sum-of-Squares, Statistical Queries, low degree polynomials) for both the distinguishing and refutation versions of the problem [ 29 , 6 , 25 , 39 , 10 , 26 ] . The connection between graph expansion properties of the constraint graph H and the conjectured hardness of noisy k -XOR associated with H is most transparent in terms of low-weight linear dependencies in the matrix A_{H} , or equivalently small even covers. Graph expansion rules out the existence of small even covers, implying local pseudorandomness, lower bounds for low-degree distinguishers, and SoS lower bounds (see Section 2

Read the complete text