Algorithms for solving noisy k-XOR problems under various noise and sample sizes
A Short Note on Algorithms For The Noisy $k$-XOR Problem
Data Structures and AlgorithmsComputational Complexity
Summary
The paper looks at when and how noisy k-XOR problems can be solved efficiently, considering how many samples and how much noise affect the process. Noisy k-XOR problems involve finding hidden patterns in data where errors or noise are present. The authors discuss known algorithms that work in different ranges of sample quantity and noise level, and they improve on one specific range where the problem can be solved faster. Their work connects these problems to finding certain structures called short cycles in complex networks.
What this means in practice
- •For coding theory engineers: Design error-correcting codes that tolerate noise using efficient solving of noisy k-XOR constraints.
- •For cryptography developers: Analyze security assumptions based on noisy k-XOR problems by applying improved algorithms for specific noise and data regimes.
A theory result. No direct application yet.
Authors
Kiril Bangachev
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 $(β, δ)$ 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 $β> δ+ k(1-δ), δ\in (0,1)$ based on a reduction to the first algorithm [DJ24,CSZ24]. IV. Extending [AF09], we strictly improve the last regime to $β> δ+ (k-1)(1-δ), δ\in (0,1).$ These algorithms correspond to efficiently finding short cycles in uniform hypergraphs and can be equivalently phrased as algorithmic Moore bounds.