A Short Note on Algorithms For The Noisy $k$-XOR Problem

Kiril Bangachev

This mostly expository note studies the sample-noise regimes in which the testing problem for noisy $k$-XOR in dimension $n$ can be efficiently solved. Concretely, we ask what pair…