Technical Summary: Hypergraph Cycle Enumeration for Efficient Inference of Planted $k$-XOR

1. Problem Statement

The paper addresses the problem of planted noisy $k$-XOR, also known as sparse Learning Parity with Noise (LPN). The goal is to detect and recover a hidden binary vector $x \in \{\pm 1\}^n$ from a set of $m$ noisy parity measurements. Each measurement consists of a support set $S_a \subseteq [n]$ of size $k$ and a label $b_a$, related by the equation:
$$b_a = \eta_a \prod_{v \in S_a} x_v$$
where $\eta_a \in \{\pm 1\}$ is a noise variable with expectation $E[\eta_a] = \rho$.

• Detection: Distinguish between the null case ($\rho=0$, random data) and the planted case ($\rho > 0$).
• Recovery: Reconstruct the hidden vector $x$.

The problem is characterized by a statistical-computational gap. While information-theoretic recovery is possible with $m = \Theta(n)$ clauses, no known polynomial-time algorithm succeeds below the threshold $m = e^{\Theta(n^{k/2})}$ for even $k \ge 4$. Existing efficient methods, such as the Kikuchi hierarchy and Sum-of-Squares (SoS), offer a "smooth trade-off" where increasing the computational degree $\ell$ allows for recovery with fewer samples, but at the cost of exponential runtime $n^{O(\ell)}$ and memory usage scaling with the dimension of a lifted space $\binom{n}{\ell}$.

2. Methodology: Hypergraph Cycle Enumeration (HCE)

The authors introduce Hypergraph Cycle Enumeration (HCE), a spectral framework inspired by Gaussian elimination. The core idea is to aggregate sets of $l$ clauses such that their supports (symmetric difference) cancel out all variables except a specific pair $\{i, j\}$.

Key Mechanisms

1. Even Covers and Witnesses:
   • An even $l$-cover is a set of $l$ distinct hyperedges where every vertex appears an even number of times. The product of their labels cancels the planted signal, leaving only noise.
   • An $(i, j)$-witness is a set of $l$ clauses whose symmetric difference is exactly $\{i, j\}$. The product of their labels yields $x_i x_j$ multiplied by a noise term.
2. The Recovery Matrix $A^{(l)}$:
   • HCE constructs an $n \times n$ matrix where the entry $A^{(l)}_{ij}$ is the sum of label products over all $(i, j)$-witnesses of level $l$.
   • Unlike the Kikuchi method, which operates on a lifted space of dimension $\binom{n}{\ell}$, HCE compresses all such chains into an $n \times n$ matrix.
   • The expected value of this matrix is proportional to the rank-one signal $xx^\top$ (plus noise), allowing recovery via spectral estimation (finding the top eigenvector).
3. Algorithm Implementation:
   • The authors employ a Meet-in-the-Middle (MITM) strategy to enumerate witnesses efficiently.
   • Clauses are split into two halves (sizes $\lceil l/2 \rceil$ and $\lfloor l/2 \rfloor$). The algorithm hashes subsets by their boundary (XOR sum) and probes for matches that form valid witnesses.
   • This reduces the memory requirement to $O(n^2 + m^{\lceil l/2 \rceil})$ and avoids the exponential memory blowup of Kikuchi matrices.

3. Key Contributions

• Introduction of HCE: A hierarchical algorithmic approach for planted noisy $k$-XOR that retains the smooth sample-time trade-off of Kikuchi/SoS methods but reduces the spectral problem to an $n \times n$ matrix at every level $l$.
• Theoretical Guarantees:
  • Detection: Proved that HCE can detect planted signals when the clause density $m/n$ satisfies a threshold curve similar to Kikuchi: $m/n = e^{\Omega(\rho^{-2}(n/l)^{k/2-1})}$. The detection result is sharp, with no logarithmic loss.
  • Recovery: Established weak recovery guarantees where the top eigenvector of $A^{(l)}$ correlates with $x$. The recovery threshold matches the Kikuchi curve up to polylogarithmic factors.
• Complexity Analysis:
  • Demonstrated that for matched levels, HCE and Kikuchi have similar leading runtime exponents (e.g., for $k=4$), but HCE uses a significantly smaller matrix representation.
  • Showed that HCE achieves a subquadratic quantum speedup for the witness search step by replacing it with a quantum walk (Tani's algorithm), reducing the complexity from $O(m^{\lceil l/2 \rceil})$ to $\tilde{O}(m^{l/3})$. The authors explicitly note that this does not refute the quartic quantum speedup of the quantum Kikuchi method, which remains valid for the practically relevant regime of large size and high noise strength.
• Empirical Performance:
  • Experiments for $k=4, 5, 6$ show that HCE matches the recovery overlap of Kikuchi at equal levels.
  • Crucially, HCE is substantially faster and more memory-efficient in the ultra-sparse regime (small clause density $C$). For example, at $n=50, k=4$, HCE solved instances in $\approx 300$ seconds compared to $\approx 5.5$ hours for Kikuchi (a $\sim 60\times$ speedup).

4. Results and Trade-offs

The paper identifies distinct regimes where HCE and Kikuchi excel:

• Ultra-Sparse Regime ($C \ll 1$): HCE is superior. The cost of enumerating $l$-clause products in HCE is low because few products collapse to a pair, while Kikuchi's lifted operator remains high-dimensional regardless of density.
• Dense Regime ($C \gtrsim 1$): Kikuchi becomes preferable. As $C$ increases, the enumeration cost in HCE grows, eventually outweighing the benefit of its smaller matrix size.
• Odd $k$: HCE applies directly to odd $k$ (with specific parity handling), whereas symmetric Kikuchi requires unbalanced lifting or vanishes for certain levels due to parity obstructions.

The authors note that while HCE matches Kikuchi's recovery performance, it does not refute the quartic quantum speedup of the Kikuchi method in the regime of large size and high noise strength, as that speedup relies on the structure of the lifted Kikuchi space which HCE compresses away.

5. Significance and Claims

The paper positions HCE as a practical and theoretically grounded alternative to the Kikuchi hierarchy. Its primary significance lies in:

1. Practical Efficiency: It solves instances in the hardest (sparsest) regimes that are currently intractable for Kikuchi due to memory and runtime constraints.
2. Conceptual Clarity: It provides a transparent "cycle enumeration" interpretation of spectral methods, linking them directly to Gaussian elimination on finite fields.
3. Smooth Trade-off: It confirms that the smooth trade-off between sample complexity and computational cost is a property of the underlying even-cover structure, achievable without the massive memory overhead of lifted spaces.

The authors modestly claim that HCE does not introduce a new statistical regime or prove a universal superiority over Kikuchi; rather, it offers a practical advantage in specific parameter regimes (ultra-sparse) and provides a new perspective on the spectral endpoint of these hierarchies. They leave open the question of whether the polylogarithmic slack in their recovery bounds can be removed via normalization, and whether a similarly large quantum speedup can be achieved for HCE's enumeration step.