{"id":"arxiv/2610.27147","url":"https://arxiv.org/abs/2610.27147","tags":["cs.DS","cs.CC","math.ST"],"score":0,"title":"A Short Note on Algorithms For The Noisy $k$-XOR Problem","domain":"cs.DS","source":"arxiv","authors":["Kiril Bangachev"],"reviews":0,"subject":"cs.DS","summary":"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 $(β, δ)$ admit algorithms running in time $n^{O(k)}$ where $m = n^β, β\\in [0,k]$ is the number of samples and $\\mathsf{Bern}(n^{-δ}),δ\\in (0,+\\infty)$ is the noise distribution. The current state-of-the-art algorithms are: I. A folklore algorithm when $β> 1, δ>1$ based on Gaussian elimination; II. A folklore algorithm when $β\\ge k/2$ based on the birthday paradox; III. A recent algorithm in the regime $β> δ+…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-19","reactions":{}}