Average-Case Reductions for $k$-XOR and Tensor PCA

1. Problem Statement

The paper investigates the computational complexity of planted noisy $k$-XOR problems and their relationship to Tensor PCA.

• Planted $k$-XOR: Given a secret signal vector $x \in \{\pm 1\}^n$, the observer sees $m$ samples. Each sample consists of a random $k$-subset of indices $\alpha = \{i_1, \dots, i_k\}$ and a noisy observation $Y = x_{i_1} \cdots x_{i_k} \cdot W$, where $W$ is a Rademacher noise variable with mean $\delta$ (flipping with probability $1/2 - \delta/2$).
• Tensor PCA: The observer sees a full order-$k$ tensor $Y = \delta x^{\otimes k} + G$, where $G$ is a symmetric Gaussian noise tensor. This corresponds to the extremely dense regime of $k$-XOR where $m \approx n^k$.
• The Gap: Both problems exhibit a "computational-statistical gap." There is a threshold for the signal-to-noise ratio (SNR) below which information-theoretic recovery is impossible, and a higher threshold below which no known polynomial-time algorithms exist.
  • For $k$-XOR with $m \approx n^{k(1+\rho)/2}$, the conjectured computational threshold is $m\delta^2 \approx n^{k/2}$ (or $\delta \approx n^{-k\rho/4}$).
  • For Tensor PCA ($\rho=1$), the threshold is $\delta \approx n^{-k/4}$.

Core Question: How do the computational hardness properties of these problems relate across different parameters: tensor order $k$, sample density $\rho$ (where $m = n^{k(1+\rho)/2}$), and noise level $\delta$? Specifically, can hardness in one regime imply hardness in another via polynomial-time average-case reductions?

2. Methodology

The authors develop a framework of polynomial-time average-case reductions that transform instances of $k$-XOR (or $k$-Gauss, the Gaussian analog) with parameters $(k, m, \delta)$ into instances with parameters $(k', m', \delta')$. The reductions preserve the planted structure and the distribution of the output up to small total variation distance.

The central primitive is Equation Resolution:
Given two equations (samples) involving the secret signal, multiply them together.
$$Y_s \cdot Y_t = (x_{\alpha_s} W_s) \cdot (x_{\alpha_t} W_t) = x_{\alpha_s \triangle \alpha_t} \cdot (W_s W_t)$$
The product $x_{\alpha_s \triangle \alpha_t}$ is a new signal term of order $k' = |\alpha_s \triangle \alpha_t|$, and the noise term $W_s W_t$ has a new bias $\delta' = \delta^2$.

The paper addresses two major challenges in making this a valid reduction:

1. Noise Dependence: Reusing the same input equation in multiple products creates statistical dependencies between output equations, violating the i.i.d. assumption of the target model.
2. Index Set Distribution: The resulting index sets $\alpha_s \triangle \alpha_t$ may not be uniformly distributed or may have structural constraints (e.g., disjointness from the intersection).

To overcome these, the authors employ two distinct resolution strategies based on the density of the input:

A. Discrete Resolution (Sparse Regime)

• Mechanism: Designed for sparse instances ($\rho < 0$ or low $\rho$).
• Strategy: Avoid reuse by design. The algorithm partitions the input equations based on their "cancellation sets" (indices that will be removed during the symmetric difference). It ensures that each input equation is used in at most one product pair.
• Result: This guarantees independence of the output noise. It allows reducing $k$-XOR to $k'$-XOR where $k' \le k(1-\rho)$, effectively trading order for density.

B. Gaussian Resolution (Dense Regime)

• Mechanism: Designed for dense instances ($\rho \ge 1/3$), including Tensor PCA.
• Strategy: Aggregate via Gram Matrices. Instead of avoiding reuse, the algorithm allows reusing inputs but switches to the Gaussian model ($k$-Gauss). It constructs a tensor flattening of the input and computes a Gram matrix ($Y^\top Y$).
• Analysis: The authors prove a new high-dimensional Central Limit Theorem (CLT) for Gramians of sparse, non-centered Gaussian matrices. This shows that despite the reuse-induced dependencies, the aggregated output converges in total variation to a Tensor PCA instance with independent Gaussian noise.
• Result: This allows reducing high-order Tensor PCA to lower-order Tensor PCA, even when the signal is very weak.

3. Key Contributions

1. Unification of $k$-XOR and Tensor PCA

The paper establishes a formal computational equivalence between the dense $k$-XOR regime ($m \approx n^k$) and standard Tensor PCA. It proves that the hardness of $k$-XOR at the computational threshold implies the hardness of Tensor PCA at its threshold, and vice versa for specific parameter ranges.

2. A Network of Average-Case Reductions

The authors construct a "hardness partial order" across the space of parameters $(k, \rho, \delta)$.

• Densifying Reductions: They show how to map a sparse $k$-XOR instance (low $\rho$) to a denser $k'$-XOR or Tensor PCA instance (high $\rho'$), trading off the tensor order $k$ for increased density.
  • Example: Reducing 7-XOR with $m=n^{3.4}$ to 3-XOR with $m \approx n^{1.4}$.
  • Example: Reducing any $k$-XOR with $\rho > 0$ to Tensor PCA ($\rho=1$).
• Order-Reducing Reductions: They provide maps that decrease the tensor order $k$ while preserving the density regime.
  • Example: Reducing 5-XOR to 4-XOR, or 7-TensorPCA to 4-TensorPCA.

3. Extension to $k$-Sparse LWE

The framework is extended to $k$-sparse Learning With Errors (LWE) over $\mathbb{Z}_q$. The resolution primitive is adapted to linear equations over rings. The authors show that for "resolution-stable" noise distributions (Uniform, Discrete Gaussian, Bounded), similar reductions hold, establishing new connections between different $k$-sparse LWE instances.

4. New Hardness Implications

By linking these problems, the paper transfers hardness conjectures:

• If $k$-XOR is hard at a specific density $\rho$, then Tensor PCA is hard at its threshold.
• The results imply that the conjectured computational-statistical gap for Tensor PCA is a consequence of the gap for sparse $k$-XOR.

4. Key Results

• Theorem 2.1 (Order Reduction): For $\rho=0$ (canonical $k$-XOR), $k$-XOR is reducible to $k'$-XOR for all $k > k'$ (with parity constraints). For $\rho=1$ (Tensor PCA), $k$-TensorPCA reduces to $k'$-TensorPCA for $k > 1.5 k'$ (even) or $k > 3k'$ (odd).
• Theorem 2.2 (Densifying Reduction): For any $\rho \in (0, 1)$, there exists a reduction from $k$-XOR at density $\rho$ to $k'$-XOR at any higher density $\rho' \in (2\rho/(1-\rho), 1]$, provided $k$ is sufficiently large.
• Theorem 2.3 (Explicit Tradeoffs): Provides explicit formulas for the relationship between input order $k$, input density $\rho$, and output order $k'$, output density $\rho'$.
• Hardness Conjecture Transfer: The paper formalizes that if the hardness conjecture $\text{CONJ}(k, \rho)$ holds (no poly-time algorithm exists), then $\text{CONJ}(k', \rho')$ holds for the reduced parameters. This establishes a hierarchy where hardness at sparse regimes implies hardness at dense regimes (Tensor PCA).

5. Significance

• Theoretical Unification: This work provides the first comprehensive framework linking the complexity of sparse planted problems ($k$-XOR) with dense planted problems (Tensor PCA). It suggests they are not isolated phenomena but part of a continuous spectrum of hardness.
• Hardness Evidence: By reducing Tensor PCA to sparse $k$-XOR, the paper strengthens the evidence for the computational hardness of Tensor PCA, a problem central to high-dimensional statistics and machine learning.
• Algorithmic Limits: The reductions define the boundaries of what is possible with polynomial-time algorithms. If a reduction exists from Problem A to Problem B, then an algorithm for B implies an algorithm for A. Conversely, hardness of A implies hardness of B.
• Cryptography: The results have implications for the security of cryptographic schemes based on $k$-XOR and $k$-sparse LWE, as they clarify the relationships between different parameter settings.
• New Techniques: The development of the "resolution-stable" noise concept and the high-dimensional CLT for sparse Gramians are novel technical tools that may be applicable to other average-case complexity problems.

In summary, the paper constructs a "map" of computational hardness for planted tensor problems, showing that the difficulty of recovering a signal in a noisy tensor is fundamentally linked to the difficulty of solving sparse linear equations over finite fields, mediated by the density of the observations.