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

Abstract

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 pairs $(\beta ,\delta )$ admit algorithms running in time $n^{O(k)}$ where $m=n^{\beta },\beta \in [0,k]$ is the number of samples and $\mathsf{Bern}(n^{-\delta }),\delta \in (0,+\infty )$ is the noise distribution. The current state-of-the-art algorithms are: I. A folklore algorithm when $\beta >1,\delta >1$ based on Gaussian elimination; II. A folklore algorithm when $\beta \ge k/2$ based on the birthday paradox; III. A recent algorithm in the regime $\beta >\delta +k(1-\delta ),\delta \in (0,1)$ based on a reduction to the first algorithm [DJ24,CSZ24]. IV. Extending [AF09], we strictly improve the last regime to $\beta >\delta +(k-1)(1-\delta ),\delta \in (0,1).$ These algorithms correspond to efficiently finding short cycles in uniform hypergraphs and can be equivalently phrased as algorithmic Moore bounds.