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

Figure 1: Sample–noise tradeoffs for noisy $k$-XOR, equivalently interpreted through finding cycles of length $\widetilde{O}(n^\delta)$. Regions strictly above and to the right of the curves are “easy” and handled by the respective algorithms. The Moore bound does not imply hardness for noisy $k$-XOR but is an obstruction to the meta-approach described in Lemma 1.1, which underlies all four algorithms.

Introduction

The noisy $k$-XOR problem is informally “linear regression over $\mathbb{F}_2$ where each sample is uniformly random $k$-sparse” (we define it rigorously below). Perhaps surprisingly, unlike standard linear regression over $\mathbb{R}$, the problem exhibits a substantial information-computation gap when $k \ge3$. In some “information-theoretically possible regimes”, there is evidence for near-exponential hardness of the problem [28]. The simple linear structure combined with strong hardness makes the noisy $k$-XOR problem useful across Learning Theory [26, 15, 17, 5, 18, 12, 11 BLR+26], Cryptography [2 DJ24, 22, 27], and Average-Case Complexity [20, 28].

Despite the prominence of the problem, we still don’t know the answer to a basic question: In what regimes is noisy $k$-XOR easy? The goal of this note is to summarize the (surprisingly limited) progress towards this question. We concretely focus on the regime of small sparsity $k = \widetilde{O}(1)$, inverse polynomial noise rate $\eta= n^{-\delta}$, $\delta\in(0,+\infty)$ and polynomially many equations $m = n^\beta$, $\beta\in(0,k]$. We also interpret easy as the existence of algorithms running in time $n^{O(k)}$. This is for two reasons. First, a lot of the interesting behavior is when $\beta= \Theta(k)$ (Figure 1), so time $n^{O(k)}$ is polynomial in the input size. Second, the recent work [6] gives evidence for an $n^{\Omega(k)}$ running-time lower bound on the noisy $k$-XOR problem.² The problem has testing, search, and refutation versions. We focus on testing and discuss the other two at the end.

The Attack: Even Cycles and An Algorithmic Moore Bound. A natural approach to Problem 1 is based on finding linearly dependent rows of $A$ (also known as even covers or cycles). This meta-approach underlies many attacks on noisy $k$-XOR and related problems including the Kikuchi matrix approach [5, 19 ABK26] and the BKW algorithm [9, 24, 23] in addition to the simple algorithms discussed below.

All the algorithms below and in Figure 1 are based on Lemma 1.1.

We note that the shortest cycle given $m=n^\beta$ equations is of size roughly $\max(2,\widetilde{O}(n^{\frac{k-2\beta}{k-2}}))$. Thus, a shortest-cycle oracle would succeed in the regime $\beta\ge\delta+ k/2(1-\delta)$. This bound is known as the Moore bound and is known to hold also for worst-case $A$ (related to the semi-random version of the problem, see § 3) [HKM23; BKN+26; Fei08]. When such cycles can be found in time $n^{O(k)}$ is a wide-open problem for both random and worst-case $A$. Even more mysterious is the regime when the noise is $n^{-\delta}$ but cycles of length $\widetilde{O}(n^\delta)$ do not exist, so one cannot rely on the approach of Lemma 1.1 even with a cycle-finding oracle.³ We outline as an interesting problem whether the converse to Lemma 1.1 holds.

Open Problem 1. Suppose that there exists an algorithm which solves the testing Problem 1 for some $(\beta,\delta)$ in time $T=T_{n,k,\beta,\delta}$. Does there exist an algorithm running in time $\operatorname{poly}(T,n^k)$ which on input $A\sim\operatorname{Sp}_{n,k}(\mathbb{F}_2)^{\otimes m}$ with $m=n^\beta$ finds a non-trivial cycle of length $n^{\delta+o(1)}$?

Algorithms

We now present the four algorithms from Figure 1 which are all based on Lemma 1.1.

I. Low-Noise Algorithm [Folklore]. When $m\ge n+1$, the first $n+1$ rows of $A$ are linearly dependent. Hence, there is a cycle of length $\le n+1$. It can be efficiently discovered in time $n^{O(1)}$ via Gaussian elimination. Combined with Lemma 1.1, this shows that the regime $\beta\ge1,\delta\ge1$ is easy.

II. Birthday Paradox Algorithm [Folklore]. Another folklore algorithm is based on the birthday paradox. Suppose that $\beta\ge k/2$. As the number of distinct rows is $n^k$, with a constant positive probability, there exist two rows among the first $n^{k/2}$ rows of $A$ that coincide. Those two rows form a cycle. Combined with Lemma 1.1, this shows that the regime $\beta\ge k/2,\delta>0$ is easy.

III. Algorithm of [DJ24; CSZ24]. In these two recent works, the authors adapt the folklore algorithm resolving $\beta\ge1,\delta\ge1$ to the regime $\beta>k-(k-1)\delta,\delta\in(0,1)$. The algorithm is the following. Consider only the first $n^\delta$ columns of $A$. Then, maintain only the rows of $A$ whose support is in those $n^\delta$ columns. A simple first and second moment calculation shows that the expected number of samples retained is $\ge n^\delta+1$. Restricting to those $n^\delta+1$ samples and $n^\delta$ columns we can apply the first algorithm.

For completeness, we give the first moment calculation. Independence across samples then implies the result. The probability that the support of a sample falls fully in the first $n^\delta$ coordinates is $\binom{n^\delta}{k}/\binom{n}{k}=\Theta((n^\delta/n)^k)$. Taking the expectation over the $m$ samples, we get an expected number of samples with support in the first $n^\delta$ columns

Hence, whenever $\beta>\delta+k(1-\delta)$, there are at least $n^\delta+1$ samples with support in the first $n^\delta$ columns as desired.

IV. Improved Algorithm Based on [3]. Finally, we present our algorithm which improves the regime of [DJ24; CSZ24] to $\beta>\delta+(k-1)(1-\delta),\delta\in(0,1)$. It is a relatively straightforward extension of an algorithm for $k=3$ in [3 Lemma 3.3].

We still separate the first $n^\delta$ columns as in algorithm III. However, this time we keep samples with exactly two coordinates outside of those $n^\delta$ columns (as opposed to 0). This is useful since those samples with exactly 2 coordinates on the remaining $n-n^\delta$ columns can be viewed as edges in a multigraph indexed by the $n-n^\delta$ columns. In graphs, unlike in hypergraphs, cycles are easy to discover.

A similar first moment + independence argument shows that whenever $\beta>\delta+(k-1)(1-\delta)+\epsilon$, with high probability there are at least $n^{1+\epsilon}$ samples which have exactly 2 coordinates outside of the first $n^\delta$ columns.

We now view those samples as a graph on $n-n^\delta$ vertices and $n^{1+\epsilon}$ edges. The following fact is well known and we only sketch its proof for completeness.

Proof Sketch. It is enough to show the existence of one such cycle. Then, we can remove its edges and induct. To show the existence of one such cycle, notice first that $G$ has a subgraph $G'=(V',E')$ with minimal degree at least $p^{\epsilon}/2$. To find one such $V'$, keep deleting vertices of degree less than $p^{\epsilon}/2$. Note that in the process at most $p \times p^{\epsilon}/2 < |E|$ edges are deleted. Hence, there are some edges which are not deleted and the process terminates with a non-empty graph. This graph has at most $p$ vertices and minimal degree $p^{\epsilon}/2$. Hence, a simple breadth-first search procedure identifies a cycle of length at most $O(\log_{p^{\epsilon}/2} p)=O(1/\epsilon)$.

The proof above not only shows that there are $n$ edge-disjoint cycles on the last $n-n^{\delta}$ columns, but it also provides an $n^{O(1)}$ algorithm for finding them. Let the cycles correspond to equations indexed by disjoint sets respectively $I_1,I_2,\ldots,I_n$, each of length $O(1/\epsilon)$. Then, the row-vectors $\mathbf{1}_{I_1}^{T}A,\mathbf{1}_{I_2}^{T}A,\ldots\mathbf{1}_{I_n}^{T}A$ fully belong to the first $n^{\delta}$ columns. Again, Gaussian elimination will give a non-trivial cycles among at most $n^{\delta}$ of them. This leads to a non-trivial cycle of length $O(n^{\delta}/\epsilon)$ of the original equations which is enough to apply Lemma 1.1.

Some Remarks

Search and Strong Refutation. This note focused on the testing problem. However, search and refutation are also of interest to the high-dimensional statistics, learning theory, and cryptography communities. We note that up to a blow-up of the sample size by a multiplicative factor of $n$ (or less) each of these algorithms can be easily transformed into a search algorithm (that is, finding $s$ under the promise that the distribution is $H_1$. For even $k$ this is only possible up to a global flip of the coordinates of $s$). This can be either seen directly for the simple algorithms we presented or via the recent search (in noisy $k$-XOR)-to-decision (in noisy $(k-1)$-XOR) reduction [11]. Prior reductions with worse sample blow-up are also known [12].

While there doesn’t seem to be a qualitative difference between search and testing, strong refutation is significantly more challenging (see [26] for the definition of refutation). In fact, Sum-of-Squares (SoS) lower bounds suggest that when $\beta\le k/2$, there are no $n^{O(k)}$ refutation algorithms.

It is worthwhile noting that the recent refutation algorithm [23] for learning parity with noise, extending the BKW algorithm, surpasses known SoS lower bounds.

Other Parameter Regimes. Our focus is on the setting of $n^{O(k)}$ time budget, $\beta\le k/2,\eta=n^{-\Omega(1)}$. However, of interest are many other regimes, such as when quasi-polynomial or even subexponential time algorithms are permissible [26 BLR+26, 25], or the noise is of the form $\operatorname{Bern}(1/2-n^{-\kappa})$ and the number of equations is $m=n^\beta$ for $\beta\in[k/2,k)$, [7] (see Section 2.1 of [7] for a similar discussion of hardness and polynomial time algorithms in that regime).

Semirandom Instances. The current note focuses on the case when $A\sim\operatorname{Sp}_{n,k}(\mathbb{F}_2)^{\otimes m}$. Common in the literature is also the semi-random case in which $A$ is worst-case, but independent of the secret and noise [18, 4]. We note that most of the discussion in the current note extends rather directly to this case as well. Neither of the algorithms relies strongly on the fact that $A$ is random. Namely, algorithm I applies directly to any $A$ (does not even need to be sparse). Algorithm II still applies as in any $k$-uniform hypergraph with $n^{k/2+\epsilon}$ edges, there is a cycle of length $O(1/\epsilon)$ which can be found in time $n^{O(k)}$ [16]. Algorithms III and IV need to be modified as follows. Note that if instead of the first $n^\delta$ columns one takes a uniformly random set of $n^\delta$ columns, the expected number of samples with $0$ (respectively $2$) coordinates outside of those columns is the same $mp$ with $p\sim n^{-(1-\delta)k}$ (respectively $p\sim n^{-(1-\delta)(k-2)}$). However, as samples are not independent, we cannot rely on a second moment concentration argument. Instead we notice that the maximal number of samples with the desired property is $m$. Hence, the probability that there are at least $mp/2$ samples with $0$ (respectively $2$) coordinates outside of those columns is at least $\frac{mp/2}{m-mp/2}=\Theta(p)=n^{-\Theta(k)}$. After $n/p$ trials we will find with high probability $mp/2$ rows that satisfy the desired property.

Hardness in Restricted Models of Computation. One reason why the complexity of the problem is still poorly understood is that we do not have any reasonable hardness predictions for the testing/search problem against restricted classes of algorithms such as via the Low-Degree Polynomials framework, Sum-of-Squares Hierarchy, or the Overlap Gap Property. While one can prove lower bounds in any of these frameworks, those lower bounds are meaningless as even the simplest algorithms – such as III and IV – do not fall in the restricted classes of algorithms (they are highly non-local and high-degree due to the Gaussian elimination step). Hence, it is not surprising that the predictions are wrong. For instance, low-degree and Sum-of-Squares predict hardness for any noise level when $\beta< k/2$. This is an expected failure mode of the two paradigms in algebraic settings (formally, the Sum-of-Squares prediction is not known to be wrong as it predicts hardness of refutation). The interesting question that it raises is:

Assuming that the problem is not easy at least in part of the “unknown regime”, we strongly believe that such a heuristic will be broadly useful towards other “algebraic” problems in high-dimensional statistics.

Alternatively, it would be interesting to prove hardness via reductions from well-established assumptions.

Acknowledgments. I am grateful to Guy Bresler, Stefan Tiegel, and Vinod Vaikuntanathan for many insightful conversations on noisy $k$-XOR and related problems.

AI Usage Statement. AI was used to discover the connection to [3]. AI was also used to revise the document.