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

Jarosław Błasiok, Paul Lou, Alon Rosen +1

In the noisy $k$-XOR problem, one is given $y\in {\mathbb{F}}_2^M$ and must distinguish between $y$ uniform and $y=Ax+e$, where $A$ is the adjacency matrix of a $k$-left-regula…