Solving Random Planted CSPs Below the n^{k/2} Threshold

Basu, Arpon; Hsieh, Jun-Ting; Lin, Andrew D.; Manohar, Peter

doi:10.4230/LIPIcs.ICALP.2026.23

Solving Random Planted CSPs Below the $n^{k/2}$ Threshold

Arpon Basu

Princeton University, NJ, USA Jun-Ting Hsieh

MIT, Cambridge, MA, USA Andrew D. Lin

Princeton University, NJ, USA Peter Manohar

The Institute for Advanced Study, Princeton, NJ, USA

Abstract

We present a family of algorithms to solve random planted instances of any $k$ -ary Boolean constraint satisfaction problem (CSP). A randomly planted instance of a Boolean CSP is generated by (1) choosing an arbitrary planted assignment $x^{*}$ , and then (2) sampling constraints from a particular “planting distribution” designed so that $x^{*}$ will satisfy every constraint. Given an $n$ variable instance of a $k$ -ary Boolean CSP with $m$ constraints, our algorithm runs in time $n^{O(\ell)}$ for a choice of a parameter $\ell$ , and succeeds in outputting a satisfying assignment if $m\geqslant O(n)\cdot(n/\ell)^{\frac{k}{2}-1}\log n$ . This generalizes the $\mathrm{poly}(n)$ -time algorithm of [17], the case of $\ell=O(1)$ , to larger runtimes, and matches the constraint number vs. runtime trade-off established for refuting random CSPs by [34].

Our algorithm is conceptually different from the recent algorithm of [23], which gave a $\mathrm{poly}(n)$ -time algorithm to solve semirandom CSPs with $m\geqslant\widetilde{O}(n^{\frac{k}{2}})$ constraints by exploiting conditions that allow a basic SDP to recover the planted assignment $x^{*}$ exactly. Instead, we forego certificates of uniqueness and recover $x^{*}$ in two steps: we first use a degree- $O(\ell)$ Sum-of-Squares SDP to find some $\widehat{x}$ that is $o(1)$ -close to $x^{*}$ , and then we use a second rounding procedure to recover $x^{*}$ from $\widehat{x}$ .

Keywords and phrases:

Random CSPs, Sparse Learning Parity with Noise

Category:

Track A: Algorithms, Complexity and Games

Funding:

Arpon Basu: This material is based upon work supported by the Moskewicz Venture Forward Graduate Fellowship and NSF CAREER Award #2047933.

Jun-Ting Hsieh: This material is based upon work supported by NSF CAREER Award #2047933.

Andrew D. Lin: This material is based upon work supported by Princeton AI Lab Seed Grant.

Peter Manohar: This material is based upon work supported by NSF Grant No. DMS-1926686

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Probabilistic algorithms

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Constraint satisfaction problems (CSPs) such as $k$ -SAT are a foundational class of computational problems that are notoriously hard in the worst case. After several decades, results on hardness of approximation show that, assuming $\mathsf{P}\neq\mathsf{NP}$ , no polynomial-time algorithm can perform much better than a naive algorithm that simply returns a random assignment when the instance is sparse: namely, it has $m=O(n)$ constraints where $n$ is the number of variables [25]. While there are efficient algorithms for “maximally dense” instances with $m\geqslant\Omega(n^{k})$ constraints [6], it is not possible to outperform a random assignment if the instance has $m=o(n^{k})$ constraints [20], assuming the Exponential-Time Hypothesis (ETH) [28]. More generally, under ETH, it is not possible for an algorithm running in time $2^{n^{\delta}}$ to outperform a random assignment if the instance has $m=o(n^{k-\delta})$ constraints [20].

Given such strong hardness results, it is natural to study the average-case search problem of solving random CSPs, where it might be possible to design substantially better algorithms than in the worst case. Although a fully random CSP (i.e., each constraint is drawn uniformly at random from all possible constraints) with $m\gg n$ constraints is unsatisfiable with high probability, one can define fairly natural models of random planted CSPs, where the instance is sampled from a “highly random” distribution but is still guaranteed to have a particular satisfying assignment $x^{*}$ .¹¹1Intuitively, one should view this distribution as first choosing an assignment $x^{*}$ to be the planted assignment, and then drawing $m$ constraints at random conditioned on each one being satisfied by $x^{*}$ . As it turns out, using such a naive process actually makes recovering $x^{*}$ rather straightforward; e.g., in the case of $k$ -SAT, the aforementioned distribution will have the negation signs associated to any variable $i\in[n]$ be biased towards the sign of $x^{*}_{i}$ , and thus a simple majority “poll” for each variable reveals the value of $x^{*}$ with high probability. Because of this, one has to choose the random constraints a bit more carefully. See Definition 2 for the formal definition of the model. This task of solving a random planted CSP has received much attention in prior works [10, 29, 12, 14, 17], with the work of [17] giving an algorithm that runs in time $\mathrm{poly}(n)$ and succeeds in solving the random planted CSP if $m\geqslant\widetilde{O}(n^{k/2})$ , which is far lower than the $m=o(n^{k-1})$ threshold for which $2^{n^{1-o(1)}}$ -time hardness is known under ETH [20]. Besides hoping to understand the complexity of CSPs better, many of these works were also motivated by the connection to Goldreich’s pseudorandom generator [22], the security of which boils down to distinguishing a random planted CSP from a fully random CSP. For example, the work of [17] implies that one can efficiently invert Goldreich’s PRG if the PRG is $k$ -local and has stretch larger than $\widetilde{O}(n^{k/2})$ .

In addition to the above average-case search problem, there is another fairly natural average-case problem for CSPs that has also received a lot of attention: refutation. In this problem, one is given a fully random CSP (which is unsatisfiable with high probability) and the algorithmic goal is to find a certificate of unsatisfiability. The refutation problem has received considerable attention over the past two decades [21, 15, 3, 8, 34], culminating in the work of [34], which gives an algorithm that, for a choice of a parameter $\ell$ , runs in $n^{O(\ell)}$ time and succeeds in refuting a random CSP with high probability provided that it has at least $m\geqslant\widetilde{O}(n)\cdot(n/\ell)^{k/2-1}$ constraints. That is, they establish a trade-off between the runtime and number of constraints required for refutation: as the “runtime exponent” $\ell$ varies from $O(1)$ to $n$ , the number of constraints required varies from $\widetilde{O}(n^{k/2})$ to $\widetilde{O}(n)$ . In particular, for the choice of $\ell=O(1)$ , this algorithm runs in $\mathrm{poly}(n)$ time and succeeds in refuting a random instance if it has at least $m\geqslant\widetilde{O}(n^{k/2})$ constraints, the same threshold as in [17]. This runtime vs. number of constraints trade-off established by [34] is conjectured to be optimal, with evidence coming in the form of lower bounds against restricted computational models such as the Sum-of-Squares (SoS) SDP hierarchy [16, 11, 33, 32, 7, 30, 18].

In light of the runtime vs. number of constraints trade-off established by [34] for the refutation problem, one may wonder if it is possible to get an algorithm with similar performance for the search problem, i.e., for random planted CSPs. While there has been a flurry of recent work on understanding refutation and search for the “harder” semirandom and smoothed CSPs [1, 24, 27, 23], there is still no known algorithm for solving random planted CSPs at the same runtime vs. number of constraints trade-off established by [34] for the refutation problem – in time $n^{O(\ell)}$ with $\widetilde{O}(n)\cdot(n/\ell)^{k/2-1}$ constraints. While there has been some recent work on designing superpolynomial-time algorithms by [13], the runtime vs. number of constraints trade-off obtained is far from the conjectured optimal one.²²2For example, the algorithm of [13] always requires at least $\Omega(n^{2})$ constraints, regardless of the runtime.

1.1 Our results

As our main result, we give, for any choice of a parameter $\ell$ , an algorithm running in time $n^{O(\ell)}$ that succeeds in outputting a satisfying assignment to a random planted $k$ -ary CSP with high probability provided that the CSP has at least $m\geqslant\widetilde{O}(n)\cdot(n/\ell)^{k/2-1}$ constraints. That is, we resolve the aforementioned gap and give an algorithm with the “correct” trade-off matching the trade-off that is known for the refutation case. Similar to [17], we can also achieve a much better dependence on $m$ by replacing $k$ with $r$ in the above expression in the case that the $k$ -ary CSP has “complexity” $r$ rather than $k$ .

Before we formally state our results, we will first formally define the random planted CSP model, as done in [17].

Definition 1 ( $k$ -ary Boolean CSPs).

A CSP instance $\Psi$ with a $k$ -ary predicate $P\colon\{-1,1\}^{k}\to\{0,1\}$ is a set of $m$ constraints on variables $x_{1},\dots,x_{n}$ of the form

P(\mathsf{neg}(C)_{1}x_{i_{1}},\mathsf{neg}(C)_{2}x_{i_{2}},\ldots,\mathsf{neg% }(C)_{k}x_{i_{k}})=1,

where $C=(i_{1},\ldots,i_{k})\in[n]^{k}$ ranges over a collection $\mathcal{H}$ of scopes³³3We additionally allow $\mathcal{H}$ to be a multiset, i.e., that multiple clauses can contain the same ordered tuple of variables. (a.k.a. clause structure) of $k$ -tuples of $n$ variables and $\mathsf{neg}(C)\in\{-1,1\}^{k}$ are “literal negations”, one for each $C$ in $\mathcal{H}$ . We let $\mathrm{val}_{\Psi}(x)$ denote the fraction of constraints satisfied by an assignment $x\in\{-1,1\}^{n}$ , and we define the value of $\Psi$ , $\mathrm{val}(\Psi)$ , to be $\max_{x\in\{-1,1\}^{n}}\mathrm{val}_{\Psi}(x)$ .

Definition 2 (Random planted $k$ -ary Boolean CSPs).

Let $P\colon\{-1,1\}^{k}\to\{0,1\}$ be a predicate. We say that a distribution $\mathcal{Q}$ over $\{-1,1\}^{k}$ is a planting distribution for $P$ if $\Pr_{y\sim\mathcal{Q}}[P(y)=1]=1$ .

We say that an instance $\Psi$ with predicate $P$ is a random planted instance with planting distribution $\mathcal{Q}$ if it is sampled from a distribution $\Psi(x^{*},m,\mathcal{Q})$ where

(1)

The planted assignment $x^{*}\in\{-1,1\}^{n}$ is arbitrary;
(2)

the scopes $\mathcal{H}\subseteq[n]^{k}$ is a multiset of size $m$ sampled by choosing $m$ elements of $[n]^{k}$ uniformly at random with replacement;
(3)

for each $C=(i_{1},\dots,i_{k})\in\mathcal{H}$ , the literal negations $\mathsf{neg}(C)$ are sampled by $\mathsf{neg}(C)\sim\mathcal{Q}(\mathsf{neg}(C)\odot(x^{*}_{i_{1}},\dots,x^{*}_% {i_{k}}))$ , where “ $\odot$ ” denotes the element-wise product of two vectors. That is, $\Pr[\mathsf{neg}(C)=y]=\mathcal{Q}(y\odot(x^{*}_{i_{1}},\dots,x^{*}_{i_{k}}))$ for each $y\in\{-1,1\}^{k}$ . Then, add the constraint

$P(\mathsf{neg}(C)_{1}x_{i_{1}},\mathsf{neg}(C)_{2}x_{i_{2}},\ldots,\mathsf{neg% }(C)_{k}x_{i_{k}})=1$

to the instance $\Psi$ .

Because $\mathcal{Q}$ is supported only on satisfying assignments to $P$ , it follows that if $\Psi\sim\Psi(x^{*},m,\mathcal{Q})$ , then $x^{*}$ satisfies $\Psi$ with probability $1$ .

Before we state our main theorem, we define the notion of distribution complexity, as defined in [17].

Definition 3 (Distribution Complexity).

Let $P:\{-1,1\}^{k}\to\{0,1\}$ be a predicate, and let $\mathcal{Q}:\{-1,1\}^{k}\to[0,1]$ be a planting distribution supported on $P^{-1}(1)$ . The distribution complexity of $\mathcal{Q}$ is defined to be the smallest integer $r\geqslant 1$ for which there exists a set $S\subseteq[k]$ of size $r$ such that $|\widehat{\mathcal{Q}}(S)|\geqslant 4^{-k}$ ,⁴⁴4The definition in [17] differs slightly here and only requires that $|\widehat{\mathcal{Q}}(S)|>0$ . This is because they implicitly assume that $\mathcal{Q}$ is constant with respect to $n$ , so that if $|\widehat{\mathcal{Q}}(S)|>0$ and $k=O(1)$ , then $|\widehat{\mathcal{Q}}(S)|\geqslant\Omega(1)$ . We do not make this assumption on $\mathcal{Q}$ . where for any set $T\subseteq[k]$ , the Fourier coefficient $\widehat{\mathcal{Q}}(T)$ is defined as $\widehat{\mathcal{Q}}(T):=2^{-k}\sum_{y\in\{-1,1\}^{k}}\mathcal{Q}(y)\prod_{j% \in T}y_{j}$ . In case $\max_{\emptyset\neq S\subseteq[k]}|\widehat{\mathcal{Q}}(S)|<4^{-k}$ , set the distribution complexity of $\mathcal{Q}$ to be $r=1$ .

Note that if $P$ is a non-trivial predicate, i.e. $P^{-1}(1)\subsetneq\{-1,1\}^{k}$ , then $\mathrm{supp}(\mathcal{Q})\neq\{-1,1\}^{k}$ since $\mathrm{supp}(\mathcal{Q})\subseteq P^{-1}(1)$ , and thus one can show (see Proposition 18) that

\max_{\emptyset\neq S\subseteq[k]}|\widehat{\mathcal{Q}}(S)|\geqslant 4^{-k}.

We now state our main theorem, which gives an algorithm to solve a random planted CSP.

Theorem 4.

Let $m, n$ be positive integers, and let $2\leqslant k\leqslant c\log n$ for some small enough constant $c>0$ . Let $\ell$ be a parameter such that $2k\leqslant\ell\leqslant n/8$ . There is an algorithm that takes as input a $k$ -ary Boolean CSP $\Psi$ and in time $n^{O(\ell)}$ outputs an assignment $x\in\{-1,1\}^{n}$ with the following guarantee: if $\Psi\sim\Psi(x^{*},m,\mathcal{Q})$ where $\mathcal{Q}$ is a planting distribution with distribution complexity $r$ and

m\geqslant m_{0}:=2^{O(k)}\cdot n\log n\cdot\max\left\{\left(\frac{n}{\ell}% \right)^{\frac{r}{2}-1},1\right\},

then with probability $\geqslant 1-1/\mathrm{poly}(n)$ over the draw of the random CSP instance $\Psi$ , it holds that the output $x$ of the algorithm is a satisfying assignment to $\Psi$ . Furthermore, the algorithm can output a list of $\leqslant 2^{k+2}$ assignments such that at least one of them is $x^{*}$ .

We note that in Theorem 4, the first term in the maximum is larger unless $r=1$ .

Theorem 4 fills the remaining gap in our knowledge for the search problem of solving random planted CSPs by giving an algorithm with “[34]-like” guarantees, i.e., an algorithm that matches the conjectured “correct” trade-off between runtime and number of constraints. We note that there is a similar gap in our knowledge for the case of semirandom CSPs, a model where the scopes $\mathcal{H}$ are additionally allowed to be worst-case. For semirandom CSPs, the works of [1, 24, 27] give a “[34]-like” refutation algorithm, and the work of [23] gives a $\mathrm{poly}(n)$ -time algorithm to solve semirandom planted CSPs with $\widetilde{O}(n^{k/2})$ constraints. However, no “[34]-like” search algorithm is known, and we leave this problem as an intriguing open question for future work. As the semirandom case is only harder than the random case handled in Theorem 4, Theorem 4 is a necessary first step towards obtaining an algorithm for the semirandom case.

Theorem 4 differs slightly from [17], which gives an algorithm to recover $x^{*}$ exactly (up to a global sign), rather than output a short list of candidate assignments, of which one is guaranteed to be $x^{*}$ and thus a satisfying one. This is because the order of quantifiers in the result of [17] is different: they allow their algorithm to depend on $\mathcal{Q}$ , i.e., it “knows” the planting distribution $\mathcal{Q}$ in advance. If we make the same assumption, then our algorithm does not need to output a list of candidate assignments, and can instead also recover $x^{*}$ exactly (up to a global sign) as well.

In Theorem 4, we assume that $\mathcal{Q}$ is a planting distribution so that it is supported only on satisfying assignments to $P$ . However, if we assume that it only outputs a satisfying assignment to $P$ with probability, say, $1-\delta$ for a constant $\delta$ , so that $\mathrm{val}_{\Psi}(x^{*})\geqslant 1-\delta-o(1)$ with high probability for $\Psi\sim\Psi(x^{*},m,\mathcal{Q})$ ,⁵⁵5 $\mathrm{val}_{\Psi}(x^{*})$ is $1-\delta$ in expectation, and by a Chernoff bound is at least $1-\delta-o(1)$ with high probability. then the algorithm still succeeds in outputting an assignment that is “just as good” as $x^{*}$ , i.e., it has value at least $1-\delta-o(1)$ as well.

Theorem 4 additionally gives an algorithm to invert Goldreich’s PRG [22] and its related variants [4] in time $n^{O(\ell)}$ when the stretch of the PRG is at least $2^{O(k)}\cdot n\cdot\left(\frac{n}{\ell}\right)^{\frac{k}{2}-1}\cdot\log n$ and $k$ is the “locality” of the PRG.

Noisy $𝒌$ -XOR / $𝒌$ -sparse LPN

We prove Theorem 4 using the reduction of [17, 23] to the special case of “noisy $k$ -XOR”, also referred to as $k$ -sparse Learning Parity with Noise (LPN). This problem was first introduced in [2], and has found many applications in cryptography such as, e.g., [5]. Below, we define the “search” or “learning” variant of the problem.

Definition 5 (Noisy $k$ -XOR / $k$ -sparse LPN instance).

We define the distribution $\mathsf{LPN}_{k}(x^{*},m,\varepsilon)$ over $k$ -XOR instances as follows:

(1)

We sample $\mathcal{H}$ by choosing $m$ tuples $C\in[n]^{k}$ with replacement;
(2)

For each $C\in\mathcal{H}$ , we set the “right-hand side” of the equation to be $b_{C}=\prod_{i\in C}x^{*}_{i}$ with probability $1/2+\varepsilon$ and $b_{C}=-\prod_{i\in C}x^{*}_{i}$ with probability $1/2-\varepsilon$ , independently.

We thus obtain a family of equations $\{\prod_{i\in C}x_{i}=b_{C}\}_{C\in\mathcal{H}}$ over $\{-1,1\}^{n}$ , which we refer to as $(\mathcal{H},\{b_{C}\}_{C\in\mathcal{H}})$ . We also refer to equations where $b_{C}=-\prod_{i\in C}x^{*}_{i}$ as corrupted or noisy.

The key technical component of the proof of Theorem 4 is the following theorem, which gives a new algorithm to recover the planted assignment $x^{*}$ from a noisy $k$ -XOR instance.

Theorem 6 (Algorithm for Noisy $k$ -XOR).

Let $m, n$ be positive integers and let $1\leqslant k\leqslant o(n^{1/4})$ . Let $\ell$ be a parameter such that $2k\leqslant\ell\leqslant n/8$ . There is an algorithm that takes as input a $k$ -XOR instance and in time $n^{O(\ell)}$ outputs an assignment $x\in\{-1,1\}^{n}$ with the following guarantee: if the input $(\mathcal{H},\{b_{C}\}_{C\in\mathcal{H}})$ is drawn from $\mathsf{LPN}_{k}(x^{*},m,\varepsilon)$ , where $\varepsilon\in(0,\frac{1}{2}]$ is such that $\varepsilon^{2}/k\geqslant\Omega(n^{-1/2})$ and

\displaystyle m\geqslant m_{0}:=2^{O(k)}\cdot n\log n\cdot\max\left\{\frac{1}{% \varepsilon^{11}}\cdot\left(\frac{n}{\ell}\right)^{\frac{k}{2}-1},\frac{1}{% \varepsilon^{2}}\right\},

(1)

then with probability $\geqslant 1-1/\mathrm{poly}(n)$ over the draw of $(\mathcal{H},\{b_{C}\}_{C\in\mathcal{H}})$ , it holds that the output $x$ satisfies $x=x^{*}$ if $k$ is odd, and either $x=x^{*}$ or $x=-x^{*}$ if $k$ is even.

We note that as in Theorem 4, the first term in Equation 1 is larger unless $k=1$ .

Theorem 6 gives a new algorithm for the search (a.k.a. “learning”) variant of $k$ -sparse LPN problem in the “high noise regime” where the noise is $1/2-\varepsilon$ . To the best of our knowledge, prior algorithms in this high noise regime were either for the distinguishing variant of the problem [3, 34, 24, 27], the search problem in the polynomial-time regime [17, 23], or are far from obtaining the conjectured optimal “runtime vs. constraints” trade-off [13].

Unlike in Theorem 4, in Theorem 6 our algorithm recovers the planted assignment $x^{*}$ exactly: when $k$ is odd, it outputs $x^{*}$ , and when $k$ is even, it outputs one of $\pm x^{*}$ , which is the best possible since $\mathsf{LPN}_{k}(x^{*},m,\varepsilon)$ and $\mathsf{LPN}_{k}(-x^{*},m,\varepsilon)$ are identical distributions. The reason we do not recover $x^{*}$ exactly in Theorem 4 is because the reduction from the general CSP case in Theorem 4 to the noisy $k$ -XOR case in Theorem 6 produces $2^{k+1}-2$ candidate noisy $t$ -XOR instances for $1\leqslant t\leqslant k$ , and then each noisy $t$ -XOR instance outputs at most $2$ candidates for $x^{*}$ because of the global sign. If we use the convention of [17] and allow the algorithm in Theorem 4 to “know” the planting distribution $\mathcal{Q}$ in advance, then it “knows” which noisy $t$ -XOR instance it should use to recover $x^{*}$ , which allows it to recover $x^{*}$ exactly (up to a global sign) as done in [17].

2 Proof Overview

In this section, we give an overview of the proofs of our two main theorems, Theorems 4 and 6. As Theorem 4 follows from Theorem 6 combined with the standard reduction from case of general CSPs to $k$ -XOR [17, 23], we will focus on Theorem 6 in this section, which is the case of noisy $k$ -XOR.

To begin, in Section 2.1 we will briefly recall the overall approach of [23] and explain why it fails to generalize to the case of super-constant $\ell$ . Then, in Section 2.2 we will explain our approach and how it avoids the previous technical barrier.

2.1 Certificates of uniqueness: the algorithm of [23]

The key idea in the algorithm of [23] is to understand conditions under which a simple SDP is able to recover the planted assignment $x^{*}$ exactly. For simplicity, let us briefly explain how this works for the case of $2$ -XOR, before explaining how this generalizes to larger $k$ .

For the case of noisy $2$ -XOR, we are given equations of the form $x_{i}x_{j}=b_{ij}$ , where $b_{ij}$ is equal to $x^{*}_{i}x^{*}_{j}$ with probability $1/2+\varepsilon$ . We can represent the pairs $\{i,j\}$ for which we are given equations as a graph $G$ , and we can view it as having a signed adjacency matrix $A$ , where $A_{i,j}=b_{ij}$ if there is an equation for the pair $\{i,j\}$ , and otherwise $A_{i,j}=0$ . The argument of [23] shows that if the (unsigned) graph $G$ is an expander with spectral gap $\lambda$ ⁶⁶6That is, $\lambda$ is the second smallest eigenvalue of the normalized Laplacian of $G$ , where the smallest eigenvalue of the normalized Laplacian is always $0$ . and $m\geqslant n\log n\cdot\mathrm{poly}(1/\lambda)$ , then with high probability over the noise, the basic SDP is able to certify that $x^{*}$ is (up to a sign) the unique globally optimal assignment. This implies that the basic SDP, which computes the matrix $X\in\mathbb{R}^{n\times n}$ that maximizes $\sum_{\{i,j\}\in G}X_{ij}b_{ij}$ subject to the conditions $X\succeq 0$ and the diagonal of $X$ is all $1$ ’s, has an optimal solution of $X=x^{*}(x^{*})^{\top}$ , and from this one can easily recover $x^{*}$ up to a sign. This is the best possible when $k$ is even, as the sign of $x^{*}$ does not matter. Finally, as $G$ is random in the case of noisy $2$ -XOR, it is also an expander, and this finishes the proof.

If $k$ is even but larger than $2$ , a similar idea still works. One can form the matrix $A$ indexed by sets $S$ of size $k/2$ , where $A(S,T)=b_{S\cup T}$ if $S\cup T=C\in\mathcal{H}$ is a constraint with right-hand side $b_{C}$ . Since the hypergraph $\mathcal{H}$ is random, this underlying graph is again an expander, and so a similar proof then shows that if $m\geqslant\widetilde{O}(N)=\widetilde{O}(n^{k/2})$ where $N=\binom{n}{k/2}$ is the number of vertices in the new graph, then one can recover $\prod_{i\in C}x^{*}_{i}$ for each $C\subseteq[n]$ of size $k$ . From this, one immediately can recover $x^{*}$ up to a global sign as well.

The barrier to the approach of [23]: weak expansion of Kikuchi graphs

The above argument shows how to give an algorithm for the “polynomial-time case” of $\ell=O(1)$ . Let us now explain why this approach fails when $\ell$ becomes super-constant. For general $\ell$ , the natural graph to consider is the “level $\ell$ Kikuchi graph” of [35], which is defined below.

Definition 7.

Let $k/2\leqslant\ell\leqslant n$ be an integer, and let $\mathcal{H}$ be a collection of subsets of $n$ of size exactly $k$ . The Kikuchi graph $G(\mathcal{H},\ell)$ is defined as follows. The vertices of the graph are the subsets $S\subseteq[n]$ of size exactly $\ell$ , and there is an edge $(S,T)$ if the symmetric difference of $S$ and $T$ is equal to some $C\in\mathcal{H}$ .

The Kikuchi graph in Definition 7 was originally introduced by [35] to give a simplified proof of the results of [34], and has since been very influential in extending algorithms for average-case $k$ -XOR instances to the superpolynomial-time and semirandom settings (see [24, 27]). In light of this, one might expect to be able to simply use this graph to extend the algorithm of [23] to prove Theorem 6. However, there is an immediate issue one encounters, which is that the Kikuchi graph is not a good expander when $\ell$ is super-constant. Even if we let $\mathcal{H}$ be the “complete” hypergraph, i.e., it contains all sets $C$ of size $k$ , then the Kikuchi graph is simply a Johnson graph. The eigenvalues and eigenvectors of the Johnson graph are well-understood (see [35, Lemma A.3]), and in this setting of parameters we will have spectral gap $\lambda\sim 1/\ell$ . Now, because the constraint threshold of [23] loses a $\mathrm{poly}(1/\lambda)$ factor, this means that if we rely on expansion here, the resulting constraint threshold we obtain will be $m_{0}\cdot\mathrm{poly}(\ell)$ instead of $m_{0}$ , where $m_{0}=\widetilde{O}(n)\left(\frac{n}{\ell}\right)^{\frac{k}{2}-1}$ is the “correct” threshold. When $\ell=O(1)$ as in the case of [23], this extra $\mathrm{poly}(\ell)$ factor is irrelevant and one obtains a threshold of $\widetilde{O}(n^{k/2})$ , but in the more general setting of Theorem 6, this is a significant loss. Furthermore, we do not see a way to overcome this barrier, as the complete hypergraph is in some sense the “best case scenario” for the algorithm.

2.2 A two part rounding procedure: our approach

The problem in the aforementioned approach arises because we are trying to find an algorithm that recovers $x^{*}$ in “one shot” by certifying that $x^{*}$ is the globally optimal assignment. Instead, to prove Theorem 6, we will depart from this framework and find $x^{*}$ in two steps. In the first step, we will be content with finding an assignment $\widehat{x}$ that is $o(1)$ -close to $x^{*}$ in normalized Hamming distance. Then, we will explain how, given $\widehat{x}$ , we can then round it to recover $x^{*}$ exactly.

Finding an approximate solution

Our algorithm for finding an approximate solution uses the Sum-of-Squares hierarchy; we refer the reader to Section 3.1 for the relevant background. As notation, we will let $\mathcal{H}$ denote the hypergraph of the noisy $k$ -XOR instance. We will think of each right-hand side $b_{C}$ as being sampled via a two step process. First, with probability $2\varepsilon$ , we set $b_{C}=x^{*}_{C}$ , and otherwise we set $b_{C}=\sigma_{C}$ , where $\sigma_{C}$ is a Rademacher random variable, i.e., it is uniform over $\{-1,1\}$ . We let $\mathcal{H}_{2\varepsilon}$ denote the set of $C$ ’s where the sampling procedure sets $b_{C}=x^{*}_{C}$ in the first step, so that for $C\in\mathcal{H}\setminus\mathcal{H}_{2\varepsilon}$ , we have $b_{C}=\sigma_{C}$ where $\sigma_{C}$ is a Rademacher random variable.

In our proof, we argue the following. Suppose that with high probability over the draw of the noisy $k$ -XOR instance, there are degree- $O(\ell)$ Sum-of-Squares proofs that certify:

(1)

(Lemma 24) For all $x\in\{-1,1\}^{n}$ , $\left|\operatorname*{\mathbb{E}}_{C\sim\mathcal{H}_{2\varepsilon}}[\prod_{i\in C% }x_{i}]-\frac{1}{n^{k}}(\sum_{i=1}^{n}x_{i})^{k}\right|\leqslant o(1)$ ;
(2)

(Fact 15) For all $x\in\{-1,1\}^{n}$ , $\left|\operatorname*{\mathbb{E}}_{C\sim\mathcal{H}\setminus\mathcal{H}_{2% \varepsilon}}[\sigma_{C}\prod_{i\in C}x_{i}]\right|\leqslant o(\varepsilon)$ , where the $\sigma_{C}$ ’s are Rademacher random variables.

Assuming that degree- $O(\ell)$ SoS can certify the above two inequalities, we can complete the proof. By a Chernoff bound, we have that $\left|\mathcal{H}_{2\varepsilon}\right|\approx 2\varepsilon m$ , where $m=\left|\mathcal{H}\right|$ . Let $\operatorname*{\widetilde{\mathbb{E}}}_{\mu}$ denote the degree- $O(\ell)$ pseudoexpectation we find by maximizing the polynomial $\psi(x)=\sum_{C\in\mathcal{H}}b_{C}\prod_{i\in C}x_{i}$ subject to the constraints $x_{i}^{2}=1$ for all $i\in[n]$ . We have $\psi(x^{*})\geqslant 2\varepsilon(1-o(1))m$ (in expectation over the noisy $k$ -XOR instance, $\psi(x^{*})=2\varepsilon m$ , and then it is $2\varepsilon(1-o(1))m$ with high probability), and so we must have $\operatorname*{\widetilde{\mathbb{E}}}_{\mu}[\psi(x)]\geqslant 2\varepsilon(1-% o(1))m$ . We can then split $\psi(x)$ as

\psi(x)=\underbrace{\sum_{C\in\mathcal{H}_{2\varepsilon}}b_{C}\prod_{i\in C}x_% {i}}_{(\operatorname{I})}+\underbrace{\sum_{C\in\mathcal{H}\setminus\mathcal{H% }_{2\varepsilon}}b_{C}\prod_{i\in C}x_{i}}_{(\operatorname{II})}.

Let $\psi_{1}(x)$ denote the first term and $\psi_{2}(x)$ denote the second term. For each $C\in\mathcal{H}\setminus\mathcal{H}_{2\varepsilon}$ , we have $b_{C}=\sigma_{C}$ . Therefore, by Item (2), degree- $O(\ell)$ SoS can certify that $\psi_{2}(x)\leqslant o(\varepsilon m)$ for all $x\in\{-1,1\}^{n}$ , which implies that $\operatorname*{\widetilde{\mathbb{E}}}_{\mu}[\psi_{2}(x)]\leqslant o(% \varepsilon m)$ . For the first term, we have that $b_{C}=\prod_{i\in C}x^{*}_{i}$ for all $C\in\mathcal{H}_{2\varepsilon}$ , and so by Item (1), it follows that $\left|\operatorname*{\widetilde{\mathbb{E}}}_{\mu}[\frac{1}{2\varepsilon m}% \psi_{1}(x)]-\operatorname*{\widetilde{\mathbb{E}}}_{\mu}[\frac{1}{n^{k}}(\sum% _{i=1}^{n}x_{i}x^{*}_{i})^{k}]\right|\leqslant o(1)$ .

Combining, we have shown that

	$\displaystyle\operatorname{\widetilde{\mathbb{E}}}_{\mu}\left[\frac{1}{n^{k}}% \langle x,x^{}\rangle^{k}\right]$	$\displaystyle\geqslant\frac{1}{2\varepsilon m}\operatorname{\widetilde{% \mathbb{E}}}_{\mu}[\psi_{1}(x)]-o(1)=\frac{1}{2\varepsilon m}\operatorname{% \widetilde{\mathbb{E}}}_{\mu}[\psi(x)-\psi_{2}(x)]-o(1)$
		$\displaystyle\geqslant\frac{1}{2\varepsilon m}\left(2\varepsilon(1-o(1))m-o(% \varepsilon m)\right)-o(1)\geqslant 1-o(1).$

Hence, $\operatorname*{\widetilde{\mathbb{E}}}_{\mu}[\frac{1}{n^{k}}\langle x,x^{*}% \rangle^{k}]$ is very close to $1$ . From this, we would like to recover an assignment $\widehat{x}$ that is $o(1)$ -close in relative Hamming distance to $x^{*}$ . In the case of odd $k$ , we do this by proving a generalization of [26, Lemma A.5] (see Fact 14), which shows that we can round by taking $\widehat{x}_{i}=\mathrm{sgn}(\operatorname*{\widetilde{\mathbb{E}}}_{\mu}[x_{i% }])$ . The case of even $k$ is slightly more complicated, as $\operatorname*{\widetilde{\mathbb{E}}}_{\mu}[x_{i}]$ may be $0$ for all $i$ because $x^{*}$ and $-x^{*}$ are equally valid planted assignments. We show that almost all of the rows of the matrix $\operatorname*{\widetilde{\mathbb{E}}}_{\mu}[x^{\otimes 2}]\in\mathbb{R}^{n% \times n}$ must be highly correlated with $x^{*}$ (see Lemma 20), and from this we can extract a single $\widehat{x}\in\{-1,1\}^{n}$ that is $o(1)$ -close to one of $x^{*}$ , $-x^{*}$ .

It remains to justify why degree- $O(\ell)$ SoS can certify Items (1) and (2) above. Item (2) is equivalent to requiring that the algorithm of [34, 35, 24, 27] for refuting random $k$ -XOR can be “captured” by degree- $O(\ell)$ SoS, which is indeed true (see Fact 15). Item (1) is a bit tricker to argue, but it turns out that we can reduce Item (1) to the case of Item (2) by using a symmetrization argument: we can replace $\frac{1}{n^{k}}(\sum_{i=1}^{n}x_{i})^{k}$ with $\operatorname*{\mathbb{E}}_{C\in\mathcal{H}^{\prime}}[\prod_{i\in C}x_{i}]$ , where $\mathcal{H}^{\prime}$ is a random hypergraph with the same distribution as $\mathcal{H}_{2\varepsilon}$ and then view the random process of placing $C$ in $\mathcal{H}_{2\varepsilon}$ or $\mathcal{H}^{\prime}$ as assigning a Rademacher random variable $\sigma_{C}$ to each $C$ . Item (2) is captured by Lemma 24, a proof of which can be found in the full-version of the paper.

As we can solve a degree- $O(\ell)$ SoS program in time $n^{O(\ell)}$ , it follows that in $n^{O(\ell)}$ time we can approximately recover $x^{*}$ by finding an assignment $\widehat{x}\in\{-1,1\}^{n}$ that is $o(1)$ -close to $x^{*}$ .

Rounding an approximate solution to an exact solution

It remains to show how to round $\widehat{x}$ to exactly recover $x^{*}$ . We will do this by using $\geqslant n\log n$ “fresh” constraints. That is, we divide the original $m$ constraints into two sets, and we use the first set to obtain $\widehat{x}$ , and the second set to round $\widehat{x}$ to get $x^{*}$ .

By “shifting” all equations by $\widehat{x}$ , we can equivalently view this rounding task as recovering a planted assignment $y$ from a noisy $k$ -XOR instance with $n\log n$ constraints under the assumption that $y$ has at most $o(n)$ entries that are $-1$ . This is because $\widehat{x}\odot x^{*}$ , where $x^{*}$ is the original assignment and $\odot$ denotes the element-wise product of vectors, has at most $o(n)$ entries that are $-1$ .

Let us now look at all constraints that contain some fixed $i\in[n]$ . By concentration, we should expect to have about $\log n$ of these constraints for each choice of $i$ , and moreover each constraint, after removing the chosen index $i$ , is distributed as a random set of size $k-1$ . We can now make the following observation. Because $y$ has only $o(n)$ entries that are $-1$ , a random set of size $k-1$ should typically avoid all $j$ ’s where $y_{j}=-1$ . Therefore, a typical constraint $C\cup\{i\}$ where $\left|C\right|=k-1$ will have $\prod_{j\in C}y_{j}=1$ , and so it will have $b_{C}=y_{i}\prod_{j\in C}y_{j}=y_{i}$ when the constraint is not noisy. Because all but a $o(1)$ -fraction of such constraints are typical, by taking a majority vote we can recover each $y_{i}$ exactly with high probability, and therefore recover the planted assignment $y$ .

The idea underpinning the above rounding procedure is simple: if $y$ is a very biased assignment, then a typical constraint contains only indices $j$ where $y_{j}=1$ , and so if we look at all constraints containing a certain index $i$ , then the right-hand sides of these equations will be biased towards $y_{i}$ , and this is simple to detect. We note that a similar idea was employed in the work of [12], which gave an algorithm to break Goldreich’s PRG under the condition that the predicate has “distribution complexity” $r\leqslant 2$ (Definition 3).

3 Preliminaries

We lay down some preliminaries we’ll use throughout the paper. The proofs of the statements used without proof can be found in the full version of the paper.

For any $x\in\mathbb{R}^{n}$ and any $S\subseteq[n]$ , define $x_{S}:=\prod_{i\in S}x_{i}$ . For any two vectors $x,y\in\mathbb{R}^{n}$ , we define the correlation of $x, y$ to be $\mathrm{corr}(x,y):=\langle x,y\rangle/\|x\|_{2}\|y\|_{2}$ .

For any $z\in\mathbb{R}$ , define

\mathrm{sgn}(z):=\begin{cases}1&\text{if }z\geqslant 0,\\ -1&\text{otherwise}.\end{cases}

For any vector $x\in\mathbb{R}^{n}$ , define $\mathrm{sgn}(x)\in\{\pm 1\}^{n}$ to be the entrywise application of $\mathrm{sgn}(\cdot)$ to $x$ .

The following proposition shows that if $x\in\mathbb{R}^{n}$ is correlated with $x^{*}\in\{-1,1\}^{n}$ , then $\mathrm{sgn}(x)$ is also correlated with $x^{*}$ .

Proposition 8.

Let $x\in\mathbb{R}^{n}$ be a non-zero vector, and let $x^{*}\in\{-1,1\}^{n}$ be such that $\mathrm{corr}(x,x^{*})\geqslant 1-\delta$ . Then $\mathrm{corr}(\mathrm{sgn}(x),x^{*})\geqslant 1-4\delta$ .

We define a $k$ -uniform hypergraph to be a collection of tuples of size $k$ . We also allow our hypergraphs to have repeated hyperedges, i.e., they can be multisets.

At times, it will be convenient to have notation to denote ordered tuples of length $k$ where the entries in the tuple are distinct. Towards this end, for any set $V$ , we define $V^{(k)}:=\{x\in V^{k}:\text{All entries of }x\text{ are distinct}\}$ . That is, $[n]^{k}$ is the set of tuples of length $k$ , and $[n]^{(k)}$ is the set of tuples of length $k$ where all entries are distinct.

We state the following result to pass from tuples in $[n]^{k}$ to tuples with distinct entries:

Proposition 9.

Let $k\geqslant 2$ . Then $|[n]^{k}\setminus[n]^{(k)}|/n^{k}\leqslant k^{2}/n$ . In particular, if $\mathcal{H}$ is a collection of $m$ u.a.r. samples from $[n]^{k}$ , then $|\mathcal{H}\setminus[n]^{(k)}|/|\mathcal{H}|\leqslant 2k^{2}/n$ with probability $\geqslant 1-\exp(-\Omega(mk^{2}/n))$ .

We generate a random hypergraph with $m$ hyperedges on the vertex set $V$ by sampling $m$ hyperedges from $V^{k}$ uniformly at random.

We will also need the following concentration inequality.

Fact 10 (McDiarmid’s Inequality, [31]).

Let $f:\Omega^{m}\to\mathbb{R}$ be a function such that for any $i\in[m]$ , and any $\omega_{1},\ldots,\omega_{m}\in\Omega,\omega^{\prime}_{i}\in\Omega$ , we have that $|f(\omega_{1},\ldots,\omega_{i},\ldots,\omega_{m})-f(\omega_{1},\ldots,\omega^% {\prime}_{i},\ldots,\omega_{m})|\leqslant c_{i}$ for some real numbers $c_{1},\ldots,c_{m}\geqslant 0$ . Then if $X_{1},\ldots,X_{m}\sim\Omega$ are independent, then

\Pr(|f(X_{1},\ldots,X_{m})-\operatorname*{\mathbb{E}}[f(X_{1},\ldots,X_{m})]|% \geqslant\varepsilon)\leqslant 2\exp\left(-\frac{2\varepsilon^{2}}{\sum_{i\in[% m]}c_{i}^{2}}\right).

3.1 Background on the Sum-of-Squares hierarchy

We recall some basic facts about SoS (see [19, 9] for further details). Define $\mathbb{R}[x_{1},\ldots,x_{n}]_{\leqslant t}$ to be the set of polynomials in $\mathbb{R}[x_{1},\ldots,x_{n}]$ of degree $\leqslant t$ .

Definition 11 (Pseudo-expectations over the hypercube).

For any $d\geqslant 2$ , a degree $d$ pseudo-expectation $\operatorname*{\widetilde{\mathbb{E}}}$ over $\{-1,1\}^{n}$ is a linear functional $\operatorname*{\widetilde{\mathbb{E}}}:\mathbb{R}[x_{1},\ldots,x_{n}]_{% \leqslant d}\to\mathbb{R}$ satisfying the following properties:

1.

(Normalization) $\operatorname*{\widetilde{\mathbb{E}}}[1]=1$ ,
2.

(Booleanity) $\operatorname*{\widetilde{\mathbb{E}}}[fx_{i}^{2}]=\operatorname*{\widetilde{% \mathbb{E}}}[f]$ for all $i\in[n],f\in\mathbb{R}[x_{1},\ldots,x_{n}]_{\leqslant d-2}$ ,
3.

(Positivity) $\operatorname*{\widetilde{\mathbb{E}}}[f^{2}]\geqslant 0$ for all $f\in\mathbb{R}[x_{1},\ldots,x_{n}]_{\leqslant d/2}$ .

Finally, denote by $\mathsf{SoS}_{d}$ $(\mathsf{SoS}_{\geqslant d})$ the set of all degree $d$ ( $\geqslant d$ ) pseudo-expectations over $\{-1,1\}^{n}$ .

We will make a slight abuse of terminology and use the phrase “pseudo-expectation” to mean a pseudo-expectation over $\{-1,1\}^{n}$ .

Suppose we have a function $f:\{-1,1\}^{n}\to\mathbb{R}$ , and suppose the function attains its maximum on $A\subseteq\{-1,1\}^{n}$ . It is easy to verify that the expectation operator associated to any probability distribution supported on $A$ is also a degree- $d$ pseudo-expectation for all $2\leqslant d\leqslant n$ . In particular, $\max_{x\in\{-1,1\}^{n}}f(x)\leqslant\sup_{\operatorname*{\widetilde{\mathbb{E}% }}\in\mathsf{SoS}_{d}}\operatorname*{\widetilde{\mathbb{E}}}[f]$ for all $2\leqslant d\leqslant n$ . We also note the following elementary facts about pseudo-distributions on the hypercube:

Fact 12.

Let $\operatorname*{\widetilde{\mathbb{E}}}$ be a pseudo-expectation of degree $\geqslant 2$ on the hypercube. Then:

(1)

For all $i\in[n]$ , $\operatorname*{\widetilde{\mathbb{E}}}[x_{i}]^{2}\leqslant 1$ . In general, if $\operatorname*{\widetilde{\mathbb{E}}}$ is a pseudo-expectation of degree $\geqslant d$ , and if $f\in\mathbb{R}[x_{1},\ldots,x_{n}]_{\leqslant d/2}$ , then $\operatorname*{\widetilde{\mathbb{E}}}[f]^{2}\leqslant\operatorname*{% \widetilde{\mathbb{E}}}[f^{2}]$ . In particular, for any $S\subseteq[n]$ , we have $|\operatorname*{\widetilde{\mathbb{E}}}[x_{S}]|\leqslant 1$ .
(2)

For all $f\in\mathbb{R}[x_{1},\ldots,x_{n}]_{\leqslant d-2}$ , we have $\operatorname*{\widetilde{\mathbb{E}}}\left[f\cdot\left\lVert x\right\rVert_{2% }^{2}\right]=\sum_{i}\operatorname*{\widetilde{\mathbb{E}}}[f\cdot x_{i}^{2}]=% \sum_{i}\operatorname*{\widetilde{\mathbb{E}}}[f]=n\operatorname*{\widetilde{% \mathbb{E}}}[f]$ .

The SoS algorithm can compute all moments up to degree $\leqslant d$ of some pseudo-expectation in $\sup_{\operatorname*{\widetilde{\mathbb{E}}}\in\mathsf{SoS}_{d}}\operatorname*% {\widetilde{\mathbb{E}}}[f]$ in $n^{O(d)}$ time:

Fact 13 (SoS Algorithm (Corollary 3.40 in [19])).

Let $f=f(x_{1},\ldots,x_{n})$ be a polynomial of degree $t$ with rational coefficients such that each coefficient has $\mathrm{poly}(n)$ bit complexity. Then for any $d\geqslant t$ , there exists an algorithm which on inputting $f$ and $d$ runs in time $n^{O(d)}$ and outputs $\{\alpha_{S}\}_{S\in\binom{[n]}{\leqslant d}}$ , where $|\alpha_{S}-\operatorname*{\widetilde{\mathbb{E}}}_{\mu}[x_{S}]|\leqslant 4^{-n}$ for all $S\in\binom{[n]}{\leqslant d}$ , and $\operatorname*{\widetilde{\mathbb{E}}}_{\mu}\in\arg\max_{\operatorname*{% \widetilde{\mathbb{E}}}\in\mathsf{SoS}_{d}}\operatorname*{\widetilde{\mathbb{E% }}}[f]$ . In particular in $n^{O(d)}$ time one can compute $\alpha:=\operatorname*{\widetilde{\mathbb{E}}}_{\mu}[f]$ such that $\alpha$ satisfies $\beta+2^{-n}\geqslant\alpha\geqslant\beta$ , where $\beta:=\max_{x\in\{-1,1\}^{n}}f(x)$ .

We also state a generalization of [26, Lemma A.5] which we need for “rounding/decoding” an approximately correct solution.

Fact 14.

Let $k\geqslant 2$ be any integer. Let $\operatorname*{\widetilde{\mathbb{E}}}$ be a degree $(k+2)$ pseudo-expectation on the hypercube such that $\operatorname*{\widetilde{\mathbb{E}}}[\langle x,x^{*}\rangle^{k}]\geqslant n^% {k}(1-\delta)$ , for some $x^{*}\in\{-1,1\}^{n},\delta\in(0,1)$ . Then:

(1)

If $k$ is odd, then $\operatorname*{\widetilde{\mathbb{E}}}[\langle x,x^{*}\rangle]\geqslant n(1-2\delta)$ ,
(2)

If $k$ is even, then $\operatorname*{\widetilde{\mathbb{E}}}\left[\langle x,x^{*}\rangle^{2}\right]% \geqslant n^{2}(1-2\delta)$ .

A proof of this fact can be found in the full-version of the paper.

3.2 Sum-of-Squares refutation of $𝒌$ -XOR

We now define the canonical degree $d$ SoS relaxation associated to a system of equations: For any hypergraph $\mathcal{H}$ , and any equation system $\{x_{C}=b_{C}\}_{C\in\mathcal{H}}$ , write $\psi(x):=\operatorname*{\mathbb{E}}_{C\sim\mathcal{H}}[b_{C}x_{C}]=\frac{1}{|% \mathcal{H}|}\sum_{C\in\mathcal{H}}b_{C}x_{C}$ . The canonical degree $d$ SoS relaxation associated to $\psi$ (and hence to the system of equations) is $\arg\max_{\operatorname*{\widetilde{\mathbb{E}}}\in\mathsf{SoS}_{d}}% \operatorname*{\widetilde{\mathbb{E}}}[\psi(x)]$ . By Fact 13, we can calculate any moment (up to degree $d$ ) of this relaxation in $n^{O(d)}$ time.

We crucially need the following theorem for refuting $k$ -XOR systems due to Hsieh, Kothari, and Mohanty ([27, Theorem 4.1]):

Fact 15 (Refuting $k$ -XOR Systems).

Let $k\in\mathbb{N}$ , and let $\ell$ be a parameter such that $2k\leqslant\ell\leqslant n/8$ . Let $\mathcal{H}\subseteq[n]^{(k)}$ be any hypergraph such that

|\mathcal{H}|\geqslant m_{0}:=2^{O(k)}\cdot\left(\frac{n}{\ell}\right)^{k/2-1}% \cdot\frac{n\log n}{\delta^{4}},

where $\delta\in(0,1/2)$ is an arbitrary parameter. Consider the polynomial

\psi(x):=\operatorname*{\mathbb{E}}_{C\sim\mathcal{H}}[\sigma_{C}x_{C}],

where $\{\sigma_{C}\}_{C\in\mathcal{H}}$ are i.i.d. uniform $\{-1,1\}$ -valued random variables. Then with probability $\geqslant 1-1/\mathrm{poly}(n)$ over the draw of $\{\sigma_{C}\}_{C\in\mathcal{H}}$ , for every pseudo-expectation $\operatorname*{\widetilde{\mathbb{E}}}$ of degree $\geqslant 2\ell$ , we have $|\operatorname*{\widetilde{\mathbb{E}}}[\psi(x)]|\leqslant\delta$ .

$\blacktriangleright$ Remark 16.

A few remarks are due:

(1)

[27] treats hypergraphs as collections of subsets of $[n]$ . But note that any $\mathcal{H}\subseteq[n]^{(k)}$ can be treated as a $k$ -uniform hypergraph in the sense of [27] by simply flattening tuples into sets.
(2)

The formal statement in [27, Theorem 4.1] does not state that their algorithm is “captured” by degree- $2\ell$ Sum-of-Squares in the above sense. However, their algorithm goes via showing an upper bound on the spectral norm of a certain level $\ell$ Kikuchi matrix (Definition 7), and it is straightforward to see that this reasoning is captured by a degree $2\ell$ Sum-of-Squares proof.

In this paper, it will be more convenient to work in the case where $\mathcal{H}$ is a subsample of $[n]^{k}$ , rather than $[n]^{(k)}$ . Because of this, we prove the following corollary using Proposition 9, which is essentially just Fact 15 with this other distribution.

Corollary 17.

Let $\mathcal{H}$ be a collection of $m$ u.a.r. samples from $\mathcal{K}:=[n]^{k}$ . Let $\{\sigma_{C}\}_{C\in\mathcal{H}}$ be i.i.d Rademacher random variables. If $2k\leqslant\ell\leqslant n/8$ is such that

m\geqslant\frac{2^{O(k)}}{\delta^{4}}\cdot\left(\frac{n}{\ell}\right)^{k/2-1}% \cdot n\log n

for some $\delta\in(0,1/2)$ , then for any pseudo-expectation $\operatorname*{\widetilde{\mathbb{E}}}$ of degree $\geqslant 2\ell$ , we have, with probability $\geqslant 1-1/\mathrm{poly}(n)$ over the randomness of $\mathcal{H}$ and $\{\sigma_{C}\}_{C\in\mathcal{H}}$ ,

\left|\operatorname*{\widetilde{\mathbb{E}}}\left[\operatorname*{\mathbb{E}}_{% C\sim\mathcal{H}}\sigma_{C}x_{C}\right]\right|\leqslant\delta+\frac{2k^{2}}{n}.

A proof of this fact can be found in the full-version of the paper.

3.3 CSP to $𝒌$ -XOR reduction

We describe the CSP to XOR reduction we use to reduce solving random CSPs to solving random XOR systems, which has appeared in prior work [17, 23].

Fix a positive integer $m$ , an assignment $x^{*}\in\{-1,1\}^{n}$ , a predicate $P:\{-1,1\}^{k}\to\{0,1\}$ , and a planting distribution $\mathcal{Q}$ for $P$ . Sample $\Psi\sim\Psi(x^{*},m,\mathcal{Q})$ . For any $S\subseteq[k]$ , define $\psi^{(S,+)}$ as the set of equations

\psi^{(S,+)}:=\left\{\prod_{j\in S}x_{i_{j}}=\prod_{j\in S}\mathsf{neg}(C)_{j}% \right\}_{C=(i_{1},\dots,i_{k})\in\mathcal{H}},

and define $\psi^{(S,-)}$ similarly as

\psi^{(S,-)}:=\left\{\prod_{j\in S}x_{i_{j}}=-\prod_{j\in S}\mathsf{neg}(C)_{j% }\right\}_{C=(i_{1},\dots,i_{k})\in\mathcal{H}}.

Finally, for any distribution $\mathcal{Q}:\{-1,1\}^{k}\to[0,1]$ , and any $S\subseteq[k]$ , define the Fourier coefficient

\widehat{\mathcal{Q}}(S):=\frac{1}{2^{k}}\sum_{y\in\{-1,1\}^{k}}\mathcal{Q}(y)% \prod_{j\in S}y_{j}.

We now claim that if $\mathcal{Q}$ does not have full-support (which will be the case when $P$ is a non-trivial predicate, i.e. $P^{-1}(1)\neq\{-1,1\}^{k}$ ), then it has a non-trivially large non-zero Fourier coefficient. A proof of this fact can be found in the full-version of this paper.

Proposition 18.

Let $\mathcal{Q}$ be a probability distribution on $\{-1,1\}^{k}$ such that $\mathrm{supp}(\mathcal{Q})\neq\{-1,1\}^{k}$ . Then $\max_{\emptyset\neq S\subseteq[k]}|\widehat{\mathcal{Q}}(S)|>4^{-k}$ .

With the above notation, we will use the following reduction from CSPs to $k$ -XOR from [23]:

Fact 19 (Claim 4.2, [23]).

Let $\Psi\sim\Psi(x^{*},m,\mathcal{Q})$ for some planting distribution $\mathcal{Q}$ for a nontrivial predicate $P$ . Then, for all non-empty $S\subseteq[k]$ , $\psi^{(S,+)}$ is distributed as $\mathsf{LPN}_{|S|}\left(x^{*},m,2^{k-1}\widehat{\mathcal{Q}}(S)\right)$ and $\psi^{(S,-)}$ is distributed as $\mathsf{LPN}_{|S|}\left(x^{*},m,-2^{k-1}\widehat{\mathcal{Q}}(S)\right)$ .

Furthermore, if the hypergraph of $\Psi$ is $\mathcal{H}$ , then the underlying hypergraph of $\psi^{(S,\pm)}$ is $\mathcal{H}|_{S}:=\{C|_{S}:C\in\mathcal{H}\}$ , where for any $C=(i_{1},\ldots,i_{k})\in[n]^{k}$ and $S\subseteq[k]$ , we define $C|_{S}:=(i_{j}:j\in S)$ .

4 From Planted CSPs to Noisy $𝒌$ -XOR

In this section, we present our algorithm for solving random planted CSPs and prove its guarantees (Theorem 4) using our algorithm for noisy $k$ -XOR (Theorem 6) as a subroutine. We first prove Theorem 4, using Theorem 6.

Proof of Theorem 4 from Theorem 6.

We shall show that the following algorithm satisfies all the required properties.

Algorithm 1 Solving Random Planted CSPs.

Input:

A CSP predicate $P:\{-1,1\}^{k}\to\{0,1\}$ , a CSP system $\Psi=\{P(x_{i_{1}},\ldots,x_{i_{k}})=1\}_{C=(i_{1},\dots,i_{k})\in\mathcal{H}}$ , where $\mathcal{H}\subseteq[n]^{k}$ , and a parameter $2k\leqslant\ell\leqslant n/8$ .

Output:

A vector $x\in\{-1,1\}^{n}$ .

Operation:

(1)

If $P(y)=1$ for all $y\in\{-1,1\}^{k}$ , then return $x:=\mathbf{1}$ .
(2)

Initialize $\mathcal{V}:=\emptyset$ .
(3)
For $\emptyset\neq S\subseteq[k]$ , For $\ast\in\{+,-\}$ :
1. (a)
  
  Run the algorithm of Theorem 6 (Algorithm 2) on input $(\psi^{(S,\ast)},\ell)$ to obtain output $x\in\{-1,1\}^{n}$ . Add $x,-x$ to $\mathcal{V}$ .
(4)

For every $v\in\mathcal{V}$ , check if $v$ satisfies $\Psi$ . Return the first satisfying assignment found.
(5)

If no satisfying assignment is found in the previous line, return $\mathbf{1}$ .

If $P(y)=1$ for all $y\in\{-1,1\}^{k}$ , then the CSP instance is trivially satisfiable, and the algorithm may return any vector, say $\mathbf{1}$ .

Thus assume $P^{-1}(1)\subsetneq\{-1,1\}^{k}$ , and thus $\mathrm{supp}(\mathcal{Q})\neq\{-1,1\}^{k}$ . Let $S^{*}\subseteq[k]$ be the smallest non-empty set such that $|\widehat{\mathcal{Q}}(S^{*})|\geqslant 4^{-k}$ (such a set exists due to Proposition 18). Write $r=|S^{*}|$ , and note that $r$ is the distribution complexity of $\mathcal{Q}$ .

Now, enumerate all non-empty $S\subseteq[k]$ , and for each $S$ guess if $\widehat{\mathcal{Q}}(S)$ is $>0,=0$ or $<0$ . For each $S$ where we guessed $\widehat{\mathcal{Q}}(S)>0$ (resp. $<0$ ), construct the instance $\psi:=\psi^{(S,+)}$ (resp. $\psi:=\psi^{(S,-)}$ ), run Algorithm 2 on $\psi$ and note down its output.

Consequently, we obtain a list of $4(2^{k}-1)<2^{k+2}$ outputs from the above procedure for $2^{k}-1$ different non-empty subsets of $[k]$ , $2$ possible signs of each Fourier coefficient, and another factor of $2$ to include the negation of each output when $k$ is even.

Now, note that since $\mathcal{H}$ is a collection of $m$ u.a.r. samples from $[n]^{k}$ , $\mathcal{H}|_{S^{*}}$ is a collection of $m$ u.a.r. samples from $[n]^{|S^{*}|}=[n]^{r}$ . Consequently, when we guess the sign of $\widehat{\mathcal{Q}}(S^{*})$ correctly, running Algorithm 2 on $\psi^{(S^{*},\mathrm{sgn}(\widehat{\mathcal{Q}}(S^{*})))}\sim\mathsf{LPN}_{r}% \left(x^{*},m,\varepsilon\right)$ , where $\varepsilon\geqslant 2^{k-1}\cdot 4^{-k}\geqslant 2^{-O(k)}$ , yields a vector $x\in\{\pm x^{*}\}$ with probability $\geqslant 1-1/\mathrm{poly}(n)$ , by Fact 19 and Theorem 6. Consequently, with probability $\geqslant 1-1/\mathrm{poly}(n)$ , $\mathcal{V}$ , which is a list of size $\leqslant 2^{k+2}$ , contains $x^{*}$ , which is a satisfying assignment for $\Psi$ , as desired.

Finally, the algorithm described above takes $O(2^{k})\cdot n^{O(\ell)}=n^{O(\ell)}$ time to run, as $\ell\geqslant 2k$ . $\hfill\blacktriangleleft$

5 Solving Noisy $𝒌$ -XOR

In this section, we prove Theorem 6, which is our algorithm to solve noisy $k$ -XOR instances, or equivalently $k$ -sparse LPN. As explained in Section 2, the algorithm of Theorem 6 proceeds in two steps. First, we will recover an approximate solution $\widehat{x}$ is that is close to $x^{*}$ , and then we will round $\widehat{x}$ to recover $x^{*}$ (up to a global sign). The two steps are captured by the following two lemmas below, which we will prove in Sections 5.1 and 5.2, respectively.

Lemma 20 (Finding an approximate solution).

Let $m, n$ be positive integers, and let $2\leqslant k\leqslant o(n^{1/4})$ . Let $\ell$ be a parameter such that $2k\leqslant\ell\leqslant n/8$ . There is an algorithm that takes as input a $k$ -XOR instance $(\mathcal{H},\{b_{C}\}_{C\in\mathcal{H}})$ and in time $n^{O(\ell)}$ outputs an assignment $\widehat{x}\in\{-1,1\}^{n}$ with the following guarantee. Suppose that $(\mathcal{H},\{b_{C}\}_{C\in\mathcal{H}})\sim\mathsf{LPN}_{k}(x^{*},m,\varepsilon)$ , where $\varepsilon\in(0,\frac{1}{2}]$ and

\displaystyle m\geqslant\frac{2^{O(k)}}{\varepsilon^{6}\delta^{5}}\cdot\left(% \frac{n}{\ell}\right)^{k/2-1}\cdot n\log n

(2)

for some $\delta\in(0,1/2)$ , such that $\varepsilon\delta\geqslant\Omega(n^{-1/2})$ for some large enough constant in the $\Omega(\cdot)$ . Then with probability at least $1-1/\mathrm{poly}(n)$ , it holds that

(1)

If $k$ is odd, then $\mathrm{corr}(\widehat{x},x^{*})\geqslant 1-\delta$ ;
(2)

If $k$ is even, then either $\mathrm{corr}(\widehat{x},x^{*})\geqslant 1-\delta$ or $\mathrm{corr}(-\widehat{x},x^{*})\geqslant 1-\delta$ .

Lemma 21 (Rounding an approximate solution to an exact solution).

Let $m, n$ be positive integers and let $2\leqslant k\leqslant o(\sqrt{n})$ . There is an algorithm that takes as input a $k$ -XOR instance $(\mathcal{H},\{b_{C}\}_{C\in\mathcal{H}})$ along with an assignment $\widehat{x}\in\{-1,1\}^{n}$ , and in time $\mathrm{poly}(m,n)$ outputs an assignment $\widetilde{x}\in\{-1,1\}^{n}$ with the following guarantee. If $(\mathcal{H},\{b_{C}\}_{C\in\mathcal{H}})\sim\mathsf{LPN}_{k}(x^{*},m,\varepsilon)$ where $\mathrm{corr}(\widetilde{x},x^{*})\geqslant 1-\delta$ (if $k$ is odd) or $\left|\mathrm{corr}(\widetilde{x},x^{*})\right|\geqslant 1-\delta$ (if $k$ is even) for some $\delta$ such that $\delta\leqslant\frac{\varepsilon}{k}$ , and if $m\geqslant\Omega(\varepsilon^{-2}n\log n)$ , then with probability $\geqslant 1-1/\mathrm{poly}(n)$ over the draw of the noisy $k$ -XOR instance, the output $\widetilde{x}$ satisfies $\widetilde{x}=x^{*}$ (if $k$ is odd) or $\widetilde{x}\in\{x^{*},-x^{*}\}$ (if $k$ is even).

We now prove Theorem 6 from Lemmas 20 and 21.

Proof of Theorem 6 from Lemmas 20 and 21.

We shall show that the following algorithm satisfies all the required properties:

Algorithm 2 Recovering

x^{*}

from Noisy XOR system.

Input:

A system of $k$ -XOR equations $(\mathcal{H},\{b_{C}\}_{C\in\mathcal{H}})$ , where $\mathcal{H}\subseteq[n]^{k}$ , and a parameter $2k\leqslant\ell\leqslant n/8$ .

Output:

A vector $x\in\{-1,1\}^{n}$ .

Operation:

(1)
If $k\geqslant 2$ :
1. (a)
  
  Split $\mathcal{H}$ into two parts $\mathcal{H}=\mathcal{H}_{1}\sqcup\mathcal{H}_{2}$ with $|\mathcal{H}_{1}|=\lceil|\mathcal{H}|/2\rceil,|\mathcal{H}_{2}|=\lfloor|% \mathcal{H}|/2\rfloor$ .
2. (b)
  
  Run the algorithm of Lemma 20 (Algorithm 3) on input $(\mathcal{H}_{1},\{b_{C}\}_{C\in\mathcal{H}_{1}})$ , and let $\widehat{x}$ denote the output.
3. (c)
  
  Run the algorithm of Lemma 21 (Algorithm 4) on input $(\widehat{x},\mathcal{H}_{2},\{b_{C}\}_{C\in\mathcal{H}_{2}})$ , and let $\widetilde{x}$ denote the output. Return $\widetilde{x}$ .
(2)
Else if $k=1$ :
1. (a)
  
  For every $i\in[n]$ , collect all equations of the form $\{x_{i}=b_{i_{j}}\}$ , and return $x\in\{-1,1\}^{n}$ , where $x_{i}:=\operatorname{majority}(\{b_{i_{j}}\})$ .

First assume $k\geqslant 2$ , and write $\delta:=\varepsilon/k$ . Split $\mathcal{H}$ into two parts $\mathcal{H}=\mathcal{H}_{1}\sqcup\mathcal{H}_{2}$ with $|\mathcal{H}_{1}|=\lceil m/2\rceil,|\mathcal{H}_{2}|=\lfloor m/2\rfloor$ . Note that $|\mathcal{H}_{2}|\geqslant\Omega(\varepsilon^{-2}n\log n)$ . We now make cases:

(1)

$𝒌$ odd: In this case, applying Lemma 20 in Step (1b), with probability $1-1/\mathrm{poly}(n)$ we obtain $\widehat{x}\in\{-1,1\}^{n}$ with $\mathrm{corr}(\widehat{x},x^{*})\geqslant 1-\delta=1-\varepsilon/k$ . Now, note that the distribution of $\{\mathcal{H}_{1},\{b_{C}\}_{C\in\mathcal{H}_{1}}\}$ (which includes the randomness of $\mathcal{H}_{1}$ and the randomness of $\{b_{C}\}$ ) is independent of $\{\mathcal{H}_{2},\{b_{C}\}_{C\in\mathcal{H}_{2}}\}$ . Since $\widetilde{x}$ is completely determined by $\{\mathcal{H}_{1},\{b_{C}\}_{C\in\mathcal{H}_{1}}\}$ , $\widetilde{x}$ is independent of $\{\mathcal{H}_{2},\{b_{C}\}_{C\in\mathcal{H}_{2}}\}$ . Consequently, we can apply Lemma 21 to recover $x^{*}$ with probability $\geqslant 1-1/\mathrm{poly}(n)$ , as desired.
(2)

$𝒌$ even: In this case, applying Lemma 20 in Step (1b), with probability $1-1/\mathrm{poly}(n)$ we obtain $\widehat{x}\in\{-1,1\}^{n}$ such that $\left|\mathrm{corr}(\widehat{x},x^{*})\right|\geqslant 1-\delta$ . Again, by the same argument as in Item (1), we have that $\widetilde{x}$ is independent of $\{\mathcal{H}_{2},\{b_{C}\}_{C\in\mathcal{H}_{2}}\}$ . Consequently, we can apply Lemma 21 to recover $x^{*}$ up to a sign with probability $\geqslant 1-1/\mathrm{poly}(n)$ , as desired.

Observe that for $k\geqslant 2$ , the runtime of the algorithm is $n^{O(\ell)}+\mathrm{poly}(m,n)\leqslant n^{O(\ell)}$ , using the runtime bounds in Lemmas 20 and 21.

Finally, suppose $k=1$ . Note that for any $i\in[n]$ , the expected multiplicity of $(i)$ in $\mathcal{H}$ is $|\mathcal{H}|/n$ . Consequently, by Chernoff $+$ union bound, with probability $\geqslant 1-1/\mathrm{poly}(n)$ , for every $i\in[n]$ , we have $\geqslant\Omega(\varepsilon^{-2}\log n)$ equations of the form $\{x_{i}=b_{i_{j}}\}$ . Furthermore, $b_{i_{j}}=x^{*}_{i}$ with probability $\geqslant 1/2+\varepsilon$ , and consequently, $\operatorname{majority}(\{b_{i_{j}}\})=x^{*}_{i}$ with probability $\geqslant 1-\exp(-\Omega(\varepsilon^{2}\cdot(\varepsilon^{-2}\log n)))% \geqslant 1-1/\mathrm{poly}(n)$ , and the theorem follows by a union bound over all $i\in[n]$ . $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 22.

A few remarks are due:

(1)

Note that Algorithm 2 doesn’t assume knowledge of $\varepsilon$ . Algorithm 2 only assumes knowledge of $\ell$ , which should be viewed as a proxy for the amount of runtime we have available. Given $\ell$ , if $\varepsilon$ is large enough (as dictated by Equation 1), then we recover $x^{*}$ successfully.
(2)

By [27, Remark 2], for even $k$ , we can actually take $m_{0}:=2^{O(k)}\cdot\left(\frac{n}{\ell}\right)^{k/2-1}\cdot\frac{n\log n}{% \delta^{2}}$ , as opposed to the $\delta^{-4}$ dependence right now in Fact 15. Tracking the dependence of $\delta$ throughout the proof of Theorem 6, for even $k$ , we can take

$m_{0}:=\frac{2^{O(k)}}{\varepsilon^{7}}\cdot\left(\frac{n}{\ell}\right)^{k/2-1% }\cdot n\log n,$

in Equation 1, instead of the $\varepsilon^{-11}$ dependence.

5.1 Finding an approximate solution: proof of Lemma 20

In this subsection, we prove Lemma 20. We do this by showing that the algorithm below has the required guarantees.

Algorithm 3 Recovering

x^{*}

from Noisy XOR system.

Input:

A system of equations $(\mathcal{H},\{b_{C}\}_{C\in\mathcal{H}})$ and a parameter $2k\leqslant\ell\leqslant n/8$ .

Output:

A vector $x\in\{-1,1\}^{n}$ .

Operation:

(1)
If $k$ is odd:
1. (i)
  
  Compute $x^{\prime}:=\operatorname*{\widetilde{\mathbb{E}}}_{\mu}[x]$ , where $\operatorname*{\widetilde{\mathbb{E}}}_{\mu}\in\arg\max_{\operatorname*{% \widetilde{\mathbb{E}}}\in\mathsf{SoS}_{2\ell}}\operatorname*{\widetilde{% \mathbb{E}}}[\sum_{C\in\mathcal{H}}b_{C}x_{C}]$ .
2. (ii)
  
  Output $\widehat{x}:=\mathrm{sgn}(x^{\prime})$ .
(2)
Else if $k$ is even:
1. (i)
  
  Compute $X:=\operatorname*{\widetilde{\mathbb{E}}}_{\mu}[x^{\otimes 2}]\in\mathbb{R}^{n% \times n}$ , where $\operatorname*{\widetilde{\mathbb{E}}}_{\mu}\in\arg\max_{\operatorname*{% \widetilde{\mathbb{E}}}\in\mathsf{SoS}_{2\ell}}\operatorname*{\widetilde{% \mathbb{E}}}[\sum_{C\in\mathcal{H}}b_{C}x_{C}]$ .
2. (ii)
  
  For each row $X^{(i)}$ of $X$ , compute $\widehat{x}^{(i)}:=\mathrm{sgn}(X^{(i)})$ .
3. (iii)
  
  For each $i,j\in[n]$ , compute $\left|\mathrm{corr}(\widehat{x}^{(i)},\widehat{x}^{(j)})\right|$ . For each $i\in[n]$ , let $\delta_{i}$ be such that $\left|\mathrm{corr}(\widehat{x}^{(i)},\widehat{x}^{(j)})\right|\geqslant 1-% \delta_{i}$ for at least $0.99n$ choices of $j\in[n]$ . Let $i^{*}\in[n]$ be a minimizer of $\delta_{i}$ . Output $\widehat{x}^{(i^{*})}$ .

We start by showing that the canonical degree $2\ell$ SoS program recovers a vector which is strongly correlated with $x^{*}$ .

Observe that in Step (1i) or Step (2i), Algorithm 3 first finds a pseudoexpectation which maximizes $\operatorname*{\widetilde{\mathbb{E}}}[\sum_{C\in\mathcal{H}}b_{C}x_{C}]$ . We show that for such a pseudodistribution, $\operatorname*{\widetilde{\mathbb{E}}}[\sum_{C\in\mathcal{H}}b_{C}x_{C}]$ is close to $\operatorname*{\widetilde{\mathbb{E}}}[\langle x,x^{*}\rangle^{k}]$ (when we normalize appropriately) with high probability over the choice of a random XOR instance, which we use to bound the correlation.

Lemma 23.

Let $2\leqslant k\leqslant o(n^{1/4})$ , and let $(\mathcal{H},\{b_{C}\}_{C\in\mathcal{H}})\sim\mathsf{LPN}_{k}(x^{*},m,\varepsilon)$ , where $\varepsilon\in(0,\frac{1}{2}]$ . Let $\ell$ be a parameter such that $2k\leqslant\ell\leqslant n/8$ , and suppose

\displaystyle m\geqslant\frac{2^{O(k)}}{\varepsilon\delta^{5}}\cdot\left(\frac% {n}{\ell}\right)^{k/2-1}\cdot n\log n,

(3)

where $\delta\in(0,1/2)$ is a parameter. Then with probability $\geqslant 1-1/\mathrm{poly}(n)$ over the draw of $\mathcal{H}$ and $\{x_{C}=b_{C}\}_{C\in\mathcal{H}}$ , we have that for any pseudo-expectation $\operatorname*{\widetilde{\mathbb{E}}}$ of degree $\geqslant 2\ell$ ,

\operatorname*{\widetilde{\mathbb{E}}}\left[\psi(x)-\frac{2\varepsilon}{n^{k}}% \langle x,x^{*}\rangle^{k}\right]\leqslant\delta+O\left(\frac{1}{\sqrt{n}}% \right),

where $\psi(x):=\operatorname*{\mathbb{E}}_{C\sim\mathcal{H}}[b_{C}x_{C}]$ .

Proof.

Consider the random variable

X:=\begin{cases}\sigma&\text{with probability }1-2\varepsilon,\\ 1&\text{with probability }2\varepsilon\end{cases},

where $\sigma$ is a Rademacher random variable, i.e. it takes values $\pm 1$ with equal probability. Note that $\Pr(X=1)=1-\Pr(X=-1)=\frac{1}{2}+\varepsilon$ , and thus $b_{C}$ is distributed as $X\cdot x^{*}_{C}$ . Consequently, we can write
$\displaystyle\operatorname*{\widetilde{\mathbb{E}}}\left[\sum_{C\in\mathcal{H}% }b_{C}x_{C}-\frac{2\varepsilon m}{n^{k}}\langle x,x^{*}\rangle^{k}\right]=% \underbrace{\operatorname*{\widetilde{\mathbb{E}}}\left[\sum_{C\in\mathcal{H}_% {2\varepsilon}}(x\odot x^{*})_{C}-\frac{2\varepsilon m}{n^{k}}\langle x,x^{*}% \rangle^{k}\right]}_{(\operatorname{I})}+\underbrace{\operatorname*{\widetilde% {\mathbb{E}}}\left[\sum_{C\in\mathcal{H}\setminus\mathcal{H}_{2\varepsilon}}% \sigma_{C}(x\odot x^{*})_{C}\right]}_{(\operatorname{II})},$ (4)

where $\mathcal{H}_{2\varepsilon}$ is a $2\varepsilon$ -sample of $\mathcal{H}$ , i.e. every element of $\mathcal{H}$ is included in $\mathcal{H}_{2\varepsilon}$ independently with probability $2\varepsilon$ . We now bound the above terms one by one:

Bounding term $(\operatorname{I})$ .

Write $m^{\prime}:=|\mathcal{H}_{2\varepsilon}|$ . Note that $\operatorname*{\mathbb{E}}[m^{\prime}]=2\varepsilon m$ , and by a Chernoff bound,

\displaystyle m^{\prime}\in 2\varepsilon m\cdot\left[1\pm O\left(\frac{1}{% \sqrt{n}}\right)\right]

(5)

with probability $\geqslant 1-\exp(-\Omega(\varepsilon m/n))\geqslant 1-\exp(-\Omega(\log n))% \geqslant 1-1/\mathrm{poly}(n)$ , since $\varepsilon m\geqslant 2^{O(k)}\frac{n^{\frac{k}{2}}\log n}{\ell^{\frac{k}{2}-% 1}}\geqslant 2^{O(k)}n\log n$ , since $\ell\leqslant n$ . Equivalently, $m^{\prime}\geqslant\frac{2^{O(k)}}{\delta^{5}}\cdot\frac{n^{\frac{k}{2}}\log n% }{\ell^{\frac{k}{2}-1}}$ with probability $\geqslant 1-1/\mathrm{poly}(n)$ .

To finish bounding this term, we will need the following lemma, which intuitively shows that degree- $2\ell$ Sum-of-Squares can certify that a random hypergraph with a sufficient number of samples is a good approximation of the complete hypergraph.

Lemma 24.

Let $\mathcal{H}$ be a collection of $m$ u.a.r. samples from $\mathcal{K}:=[n]^{k}$ , where $2\leqslant k\leqslant o(n^{1/4})$ . Let $\delta\in(0,1/2)$ be an arbitrary parameter. Then for any pseudo-expectation $\operatorname*{\widetilde{\mathbb{E}}}$ of degree $\geqslant 2\ell$ , where

\frac{n}{8}\geqslant\ell\geqslant 2k,\,\ell^{\frac{k}{2}-1}\geqslant 2^{O(k)}% \cdot\frac{n^{\frac{k}{2}}}{m}\cdot\frac{\log n}{\delta^{4}},

we have, with probability $\geqslant 1-1/\mathrm{poly}(n)$ over the draw of $\mathcal{H}$ ,

\operatorname*{\widetilde{\mathbb{E}}}\left[\operatorname*{\mathbb{E}}_{C\sim% \mathcal{H}}[x_{C}]-\operatorname*{\mathbb{E}}_{C\sim\mathcal{K}}[x_{C}]\right% ]\leqslant\delta+O\left(\frac{1}{\sqrt{n}}\right).

We now use Lemma 24 to finish bounding term (I).

Since $\mathcal{H}_{2\varepsilon}$ is distributed as a collection of $m^{\prime}$ u.a.r. samples of $\mathcal{K}$ , by Lemma 24, for any $\operatorname*{\widetilde{\mathbb{E}}}\in\mathsf{SoS}_{\geqslant 2\ell}$ , we have that
$\operatorname*{\widetilde{\mathbb{E}}}\left[\operatorname*{\mathbb{E}}_{C\sim% \mathcal{H}_{2\varepsilon}}[y_{C}]-\operatorname*{\mathbb{E}}_{C\sim\mathcal{K% }}[y_{C}]\right]\leqslant\delta+O\left(\frac{1}{\sqrt{n}}\right)\implies% \operatorname*{\widetilde{\mathbb{E}}}\left[\sum_{C\in\mathcal{H}_{2% \varepsilon}}y_{C}-m^{\prime}\operatorname*{\mathbb{E}}_{C\sim\mathcal{K}}y_{C% }\right]\leqslant\left(\delta+O\left(\frac{1}{\sqrt{n}}\right)\right)m^{\prime},$

where $y:=x\odot x^{*}$ .⁷⁷7Note that technically Lemma 24 is stated in terms of $x$ , but since it works for all pseudo-distributions of degree $\geqslant 2\ell$ , by translating we can put $y$ instead of $x$ . Now note that

\displaystyle\operatorname*{\mathbb{E}}_{C\sim\mathcal{K}}[y_{C}]=% \operatorname*{\mathbb{E}}_{C\sim\mathcal{K}}[(x\odot x^{*})_{C}]=\frac{1}{n^{% k}}\sum_{C\in[n]^{k}}(x\odot x^{*})_{C}=\frac{1}{n^{k}}\langle x,x^{*}\rangle^% {k}.

(6)

Consequently,

	$\displaystyle\left(\delta+O\left(\frac{1}{\sqrt{n}}\right)\right)m^{\prime}$	$\displaystyle\geqslant\operatorname{\widetilde{\mathbb{E}}}\left[\sum_{C\in% \mathcal{H}_{2\varepsilon}}y_{C}-m^{\prime}\operatorname{\mathbb{E}}_{C\sim% \mathcal{K}}y_{C}\right]$
		$\displaystyle=\operatorname{\widetilde{\mathbb{E}}}\left[\sum_{C\in\mathcal{H% }_{2\varepsilon}}y_{C}-\frac{2\varepsilon m}{n^{k}}\langle x,x^{}\rangle^{k}% \right]+\left(\frac{2\varepsilon m-m^{\prime}}{n^{k}}\right)\operatorname{% \widetilde{\mathbb{E}}}\langle x,x^{}\rangle^{k}$

\displaystyle\implies\operatorname*{\widetilde{\mathbb{E}}}\left[\sum_{C\in% \mathcal{H}_{2\varepsilon}}y_{C}-\frac{2\varepsilon m}{n^{k}}\langle x,x^{*}% \rangle^{k}\right]\leqslant\left(\delta+O\left(\frac{1}{\sqrt{n}}\right)\right% )m^{\prime}+\left|m^{\prime}-2\varepsilon m\right|\cdot\left|\frac{% \operatorname*{\widetilde{\mathbb{E}}}\langle x,x^{*}\rangle^{k}}{n^{k}}\right|.

(7)

Now, by Equation 6, we have $\frac{\operatorname*{\widetilde{\mathbb{E}}}[\langle x,x^{*}\rangle^{k}]}{n^{k% }}=\operatorname*{\widetilde{\mathbb{E}}}[\operatorname*{\mathbb{E}}_{C\sim% \mathcal{K}}[y_{C}]]=\operatorname*{\mathbb{E}}_{C\sim\mathcal{K}}[% \operatorname*{\widetilde{\mathbb{E}}}[x_{C}]]$ . By Fact 12, $\operatorname*{\widetilde{\mathbb{E}}}[x_{C}]\in[-1,1]$ for all $C\in\mathcal{K}$ , and thus $\operatorname*{\mathbb{E}}_{C\sim\mathcal{K}}\operatorname*{\widetilde{\mathbb% {E}}}[x_{C}]\in[-1,1]\implies\left|\frac{\operatorname*{\widetilde{\mathbb{E}}% }[\langle x,x^{*}\rangle^{k}]}{n^{k}}\right|\leqslant 1$ . Also, by Equation 5, $|m^{\prime}-2\varepsilon m|\leqslant O(m^{\prime}/\sqrt{n})$ . Putting all this together in Equation 7, we obtain that

\operatorname*{\widetilde{\mathbb{E}}}\left[\sum_{C\in\mathcal{H}_{2% \varepsilon}}y_{C}-\frac{2\varepsilon m}{n^{k}}\langle x,x^{*}\rangle^{k}% \right]\leqslant m^{\prime}\cdot\left(\delta+O\left(\frac{1}{\sqrt{n}}\right)+% O\left(\frac{1}{\sqrt{n}}\right)\right)\leqslant m\left(\delta+O\left(\frac{1}% {\sqrt{n}}\right)\right).

Bounding term $(\operatorname{II})$ .

Write $m^{\prime\prime}:=|\mathcal{H}\setminus\mathcal{H}_{2\varepsilon}|$ . Here we make two cases:

(1)

$m^{\prime\prime}\leqslant\delta m$ : In this case, $\operatorname*{\widetilde{\mathbb{E}}}\left[\sum_{C\in\mathcal{H}\setminus% \mathcal{H}_{2\varepsilon}}\sigma_{C}(x\odot x^{*})_{C}\right]=\sum_{C\in% \mathcal{H}\setminus\mathcal{H}_{2\varepsilon}}\sigma_{C}\operatorname*{% \widetilde{\mathbb{E}}}\left[(x\odot x^{*})_{C}\right]\leqslant m^{\prime% \prime}\leqslant\delta m$ .
(2)

$m^{\prime\prime}>\delta m$ : Note that $m^{\prime\prime}>\delta m\geqslant\frac{2^{O(k)}}{\varepsilon\delta^{4}}\cdot% \frac{n^{\frac{k}{2}}\log n}{\ell^{\frac{k}{2}-1}}\geqslant\frac{2^{O(k)}}{% \delta^{4}}\cdot\frac{n^{\frac{k}{2}}\log n}{\ell^{\frac{k}{2}-1}}$ . Also note that $\mathcal{H}\setminus\mathcal{H}_{2\varepsilon}$ is a collection of $m^{\prime\prime}$ u.a.r. samples from $\mathcal{K}:=[n]^{k}$ . Consequently, by Corollary 17, for any $\operatorname*{\widetilde{\mathbb{E}}}\in\mathsf{SoS}_{\geqslant 2\ell}$ , we have $\operatorname*{\widetilde{\mathbb{E}}}\sum_{C\in\mathcal{H}\setminus\mathcal{H% }_{2\varepsilon}}\sigma_{C}x_{C}\leqslant m^{\prime\prime}\left(\delta+\frac{2% k^{2}}{n}\right)\leqslant m\left(\delta+\frac{2k^{2}}{n}\right)$ .

Combining the above terms together, we can say that for any $\operatorname*{\widetilde{\mathbb{E}}}\in\mathsf{SoS}_{\geqslant 2\ell}$ , we have

\operatorname*{\widetilde{\mathbb{E}}}\left[\sum_{C\in\mathcal{H}\setminus% \mathcal{H}_{2\varepsilon}}\sigma_{C}x_{C}\right]\leqslant m\left(\delta+\frac% {2k^{2}}{n}\right)\leqslant m\left(\delta+O(n^{-1/2})\right),

where the last inequality follows since $k\leqslant o(n^{1/4})$ . Finally, putting everything together in Equation 4, we obtain that

\operatorname*{\widetilde{\mathbb{E}}}\left[\sum_{C\in\mathcal{H}}b_{C}x_{C}-% \frac{2\varepsilon m}{n^{k}}\langle x,x^{*}\rangle^{k}\right]\leqslant m\left(% \delta+O\left(\frac{1}{\sqrt{n}}\right)\right)+m\left(\delta+O\left(\frac{1}{% \sqrt{n}}\right)\right)

\leqslant m\left(2\delta+O\left(\frac{1}{\sqrt{n}}\right)\right),

and we absorb the $2$ in front of the $\delta$ in the $2^{O(k)}$ term in Equation 3. $\hfill\blacktriangleleft$ We can now prove the main lemma.

Proof of Lemma 20.

Write $\nu:=\varepsilon\delta$ . Note that $m\geqslant\frac{2^{O(k)}}{\varepsilon\nu^{5}}\cdot\left(\frac{n}{\ell}\right)^% {k/2-1}\cdot n\log n$ .

Let $\operatorname*{\widetilde{\mathbb{E}}}_{\mu}\in\arg\max_{\operatorname*{% \widetilde{\mathbb{E}}}\in\mathsf{SoS}_{2\ell}}\psi(x)$ be any pseudo-distribution maximizing $\psi(x):=\operatorname*{\mathbb{E}}_{C\sim\mathcal{H}}[b_{C}x_{C}]$ . By Lemma 23,

\operatorname*{\widetilde{\mathbb{E}}}_{\mu}\left[\psi(x)-\frac{2\varepsilon}{% n^{k}}\langle x,x^{*}\rangle^{k}\right]\leqslant\nu+O\left(\frac{1}{\sqrt{n}}% \right)\leqslant 2\nu\implies\operatorname*{\widetilde{\mathbb{E}}}_{\mu}[\psi% (x)]\leqslant\frac{2\varepsilon}{n^{k}}\operatorname*{\widetilde{\mathbb{E}}}_% {\mu}\langle x,x^{*}\rangle^{k}+2\nu,

where we can write $\nu+O(n^{-1/2})\leqslant 2\nu$ since $\nu=\varepsilon\delta\geqslant\Omega(n^{-1/2})$ .

Now, consider the probability distribution which places all its mass on $x^{*}$ . By Definition 11, the expectation operator associated to this distribution is a valid degree $2\ell$ pseudo-distribution over $\{-1,1\}^{n}$ . Furthermore, the expectation of $\psi(x)$ under this distribution is $\psi(x^{*})$ . Consequently, $\operatorname*{\widetilde{\mathbb{E}}}_{\mu}\psi(x)\geqslant\psi(x^{*})$ , and thus

	$\displaystyle\frac{2\varepsilon}{n^{k}}\operatorname{\widetilde{\mathbb{E}}}_% {\mu}\langle x,x^{}\rangle^{k}+2\nu$	$\displaystyle\geqslant\psi(x^{})=\operatorname{\mathbb{E}}_{C\sim\mathcal{H}% }[b_{C}x^{}_{C}]\overset{()}{\geqslant}2\varepsilon\left(1-O\left(\frac{1}{% \sqrt{n}}\right)\right)$		(8)
	$\displaystyle\implies\frac{1}{n^{k}}\operatorname{\widetilde{\mathbb{E}}}_{% \mu}\langle x,x^{}\rangle^{k}$	$\displaystyle\geqslant 1-\frac{\nu}{\varepsilon}-O\left(\frac{1}{\sqrt{n}}% \right)=:1-\xi,$		(9)

where $(\ast)$ follows with probability $\geqslant 1-1/\mathrm{poly}(n)$ by a Chernoff bound. Note that $\xi=\nu/\varepsilon+O(n^{-1/2})=\delta+O(n^{-1/2})=O(\delta)$ , since $\delta\geqslant\varepsilon\delta\geqslant\Omega(n^{-1/2})$ .

We now make cases based on whether $k$ is odd or even:

(1)

$k$ is odd: In this case, Fact 14 implies that $\operatorname*{\widetilde{\mathbb{E}}}_{\mu}[\langle x,x^{*}\rangle]\geqslant n% (1-\xi)\implies\langle\operatorname*{\widetilde{\mathbb{E}}}_{\mu}[x],x^{*}% \rangle\geqslant n(1-2\xi)$ . Write $z:=\operatorname*{\widetilde{\mathbb{E}}}_{\mu}[x]$ . Then note that $\|z\|_{2}^{2}=\sum_{i}\operatorname*{\widetilde{\mathbb{E}}}_{\mu}[x_{i}]^{2}% \overset{\text{\lx@cref{creftype~refnum}{sosbasicfacts}}}{\leqslant}n$ . Consequently, $\mathrm{corr}(z,x^{*})=\left|\langle z,x^{*}\rangle\right|/\|z\|_{2}\cdot\|x^{% *}\|_{2}\geqslant\langle z,x^{*}\rangle/n\geqslant 1-2\xi$ . Now, by Fact 13, the vector $x^{\prime}$ we compute (in Item 1i of Algorithm 2) is very close to its “idealized value” $z$ , i.e. $\|x^{\prime}-z\|_{1}\leqslant 2^{-n}$ . Since $2\xi\geqslant\Omega(n^{-1/2})\gg 2^{-n}$ , $2\xi+O(2^{-n})\leqslant O(\xi)\leqslant O(\delta)$ . Now, by Proposition 8, it follows that for $\widehat{x}:=\mathrm{sgn}(x^{\prime})$ , we have that $\mathrm{corr}(\widehat{x},x^{*})\geqslant 1-O(\delta)$ , which finishes the proof in this case.

(2)

$k$ is even: In this case, Fact 14 implies that $\operatorname*{\widetilde{\mathbb{E}}}_{\mu}[\langle x,x^{*}\rangle^{2}]% \geqslant n^{2}(1-2\xi)$ . Now, note that $\langle x,x^{*}\rangle^{2}=\langle x^{\otimes 2},x^{*\otimes 2}\rangle$ , and thus $\langle\operatorname*{\widetilde{\mathbb{E}}}_{\mu}[x^{\otimes 2}],x^{*\otimes 2% }\rangle\geqslant n^{2}(1-2\xi)$ . Write $Z:=\operatorname*{\widetilde{\mathbb{E}}}_{\mu}[x^{\otimes 2}]$ , where $Z$ is to be viewed as a $n\times n$ matrix. Then note that $\langle Z,x^{*\otimes 2}\rangle=\sum_{i\in[n]}\langle z^{(i)},x^{*}_{i}x^{*}% \rangle\geqslant n^{2}(1-2\xi)$ , where $z^{(i)}$ is the $i^{\mathrm{th}}$ row of $Z$ . Also note that $\|z^{(i)}\|_{2}^{2}=\sum_{j}\operatorname*{\widetilde{\mathbb{E}}}_{\mu}\left[% x_{i}x_{j}\right]^{2}\overset{\text{\lx@cref{creftype~refnum}{sosbasicfacts}}}% {\leqslant}\sum_{j}\operatorname*{\widetilde{\mathbb{E}}}_{\mu}\left[x^{2}_{i}% x^{2}_{j}\right]=n$ , and thus

	$\displaystyle\sum_{i\in[n]}\left\|\mathrm{corr}(z^{(i)},x^{*})\right\|$	$\displaystyle=\sum_{i\in[n]}\frac{\|\langle z^{(i)},x^{}\rangle\|}{\\|z^{(i)}\\|_% {2}\cdot\\|x^{}\\|_{2}}=\sum_{i\in[n]}\frac{\|\langle z^{(i)},x_{i}^{}x^{}% \rangle\|}{\\|z^{(i)}\\|_{2}\cdot\sqrt{n}}$
		$\displaystyle\geqslant\frac{1}{n}\sum_{i\in[n]}\left\|\langle z^{(i)},x_{i}^{}% x^{}\rangle\right\|\geqslant\frac{1}{n}\left\|\sum_{i\in[n]}\langle z^{(i)},x_{% i}^{}x^{}\rangle\right\|\geqslant n\left(1-2\xi\right).$

On the other hand, $\sum_{i\in[n]}\left|\mathrm{corr}(z^{(i)},x^{*})\right|\leqslant n$ , since $\mathrm{corr}(z^{(i)},x^{*})\in[-1,1]$ for each $i\in[n]$ . Consequently, by an averaging argument, we must have that for $\geqslant 0.99n$ indices $i\in[n]$ , $\left|\mathrm{corr}(z^{(i)},x^{*})\right|\geqslant 1-200\xi$ .

As before, if $X^{(i)}$ is the vector we compute (in Item 2ii of Algorithm 3), then $\|X^{(i)}-z^{(i)}\|_{1}\leqslant 2^{-n}$ , and thus for $\geqslant 0.99n$ indices $i\in[n]$ , we have $\left|\mathrm{corr}(X^{(i)},x^{*})\right|\geqslant 1-O(\xi)\geqslant 1-O(\delta)$ , and we can absorb the constant in $O(\cdot)$ into the lower bound for $m$ , as usual.

Now, let $\widehat{x}^{(i)}=\mathrm{sgn}(X^{(i)})$ for each $i$ . By Proposition 8, we have that $\left|\mathrm{corr}(\widehat{x}^{(i)},x^{*})\right|\geqslant 1-O(\delta)$ for at least $0.99n$ indices $i\in[n]$ . Call these indices the “good” indices. We now observe that the $i^{*}$ chosen in Item 2iii must be such that $\left|\mathrm{corr}(\widehat{x}^{(i^{*})},x^{*})\right|\geqslant 1-O(\delta)$ . Indeed, for any choice of one of the “good” $0.99n$ indices $i$ , we must have that $\left|\mathrm{corr}(\widehat{x}^{(i)},\widehat{x}^{(j})\right|\geqslant 1-O(\delta)$ for every other good $j$ , i.e., $\delta_{i}=O(\delta)$ . Therefore, for the particular $i^{*}$ chosen in Item 2iii, it follows that $\left|\mathrm{corr}(\widehat{x}^{(i^{*})},\widehat{x}^{(j})\right|\geqslant 1-% O(\delta)$ for some good index $j$ , there are $\geqslant 0.99n$ good indices. We thus conclude by triangle inequality that $\left|\mathrm{corr}(\widehat{x}^{(i^{*})},x^{*})\right|\geqslant 1-O(\delta)$ , which finishes the proof.

$\hfill\blacktriangleleft$

5.2 Rounding approximate solutions: proof of Lemma 21

In this subsection, we prove Lemma 21.

Proof.

Since $|\mathcal{H}|=\Omega(\varepsilon^{-2}n\log n)$ , and since $|[n]^{k}\setminus[n]^{(k)}|/n^{k}\leqslant O(k^{2}/n)=o(1)$ (see Proposition 9), if we write $\mathcal{H}^{\prime}:=\mathcal{H}\cap[n]^{(k)}$ , with probability $\geqslant 1-\exp(-\Omega(n))$ we have $|\mathcal{H}^{\prime}|\geqslant\Omega(\varepsilon^{-2}n\log n)$ . Note that all tuples in $\mathcal{H}^{\prime}$ have distinct entries. For every $i\in[n]$ , write $\mathcal{H}^{\langle i\rangle}:=\{C\setminus\{i\}:i\in C\in\mathcal{H}^{\prime}\}$ . Note that the $\mathcal{H}^{\langle i\rangle}$ s may have repeated hyperedges. Also for any $T\in\mathcal{H}^{\langle i\rangle}$ , denote by $(T,i)$ the tuple in $\mathcal{H}^{\prime}$ that $T$ was obtained from. Since the hyperedges of $\mathcal{H}^{\prime}$ are independent uniform samples from $[n]^{(k)}$ , the hyperedges of $\mathcal{H}^{\langle i\rangle}$ are independent uniform samples from $([n]\setminus\{i\})^{(k-1)}$ .

Consider the following algorithm:

Algorithm 4 Exact Recovery from an Approximately Correct Solution.

Input:

A $k$ -XOR instance $(\mathcal{H},\{b_{C}\}_{C\in\mathcal{H}})$ , and a vector $\widetilde{x}\in\{-1,1\}^{n}$ .

Output:

A vector $x\in\{-1,1\}^{n}$ .

Operation:

(1)

For every $i\in[n]$ , compute $S_{i}:=\{b_{(T,i)}\widetilde{x}_{T}:T\in\mathcal{H}^{\langle i\rangle}\}$ , which is a multiset over $\{-1,1\}$ . Here $\mathcal{H}^{\langle i\rangle}:=\{C\setminus\{i\}:i\in C\in\mathcal{H}\cap[n]^% {(k)}\}$ .
(2)

Output $x\in\{-1,1\}^{n}$ , where

$x_{i}:=\begin{cases}1&\text{if }\geqslant|S_{i}|/2\text{ entries of }S_{i}% \text{ are }1,\\ -1&\text{otherwise}\end{cases}.$

It is easy to see that the above algorithm runs in $\mathrm{poly}(m,n)$ time. We will argue that if $k$ is odd, then $x=x^{*}$ with probability $\geqslant 1-1/\mathrm{poly}(n)$ , and if $k$ is even, then $x\in\{x^{*},-x^{*}\}$ with probability $1-1/\mathrm{poly}(n)$ .

Let us first consider the case where $\mathrm{corr}(\widehat{x},x^{*})\geqslant 1-\delta$ (for both odd and even $k$ ). It suffices to show that $x_{i}\neq x^{*}_{i}$ with probability $\leqslant O(n^{-2})$ for all $i\in[n]$ , as then we are done by a union bound over all $i\in[n]$ .

Write $B:=\{i\in[n]:\widetilde{x}_{i}\neq x^{*}_{i}\}$ . Note that $\langle\widetilde{x},x^{*}\rangle=n-2|B|$ , and thus $|B|\leqslant\delta n/2$ . We call $T\in\mathcal{H}^{\langle i\rangle}$ good if it satisfies the following conditions:

(1)

$T\cap B=\emptyset$ ,
(2)

$b_{(T,i)}=x^{*}_{(T,i)}$ .

Note that if $T\in\mathcal{H}^{\langle i\rangle}$ is good, then $b_{(T,i)}\widetilde{x}_{T}=x^{*}_{(T,i)}\widetilde{x}_{T}=x^{*}_{(T,i)}x^{*}_{% T}=x^{*}_{i}$ . Consequently, $x_{i}\neq x^{*}_{i}$ if $<|S_{i}|/2=|\mathcal{H}^{\langle i\rangle}|/2$ elements of $\mathcal{H}^{\langle i\rangle}$ are good.

Since $\widetilde{x}$ is independent of $\mathcal{H}$ and all $\mathcal{H}^{\langle i\rangle}$ s, we see that the probability that any given element of $\mathcal{H}^{\langle i\rangle}$ does not intersect $B$ is
$\geqslant\prod_{i=1}^{k-1}\frac{n-|B|-i}{n-i}\geqslant\left(\frac{n-|B|-k}{n-k% }\right)^{k-1}\geqslant\left(\frac{1-\frac{\delta}{2}-\frac{k}{n}}{1-\frac{k}{% n}}\right)^{k-1}\geqslant 1-\frac{(k-1)\delta}{2(1-\frac{k}{n})}\geqslant 1-% \frac{k\delta}{2}\geqslant 1-\frac{\varepsilon}{2},$

where we recall $\mathcal{H}^{\langle i\rangle}$ contains independent uniformly random tuples from $([n]\setminus\{i\})^{(k-1)}$ , and $\frac{k-1}{1-k/n}\leqslant k$ for large enough $n$ . Since the noise in the equations $\{x_{C}=b_{C}\}_{C\in\mathcal{H}}$ is independent of the randomness in sampling $\mathcal{H}$ , the probability that any given element of $\mathcal{H}^{\langle i\rangle}$ is good is

\geqslant\left(1-\frac{\varepsilon}{2}\right)\left(\frac{1}{2}+\varepsilon% \right)\geqslant\frac{1}{2}+\frac{\varepsilon}{4}.

Now, by a Chernoff bound, $|\mathcal{H}^{\langle i\rangle}|\geqslant\frac{1}{2n}\cdot|\mathcal{H}^{\prime% }|=\Omega(\varepsilon^{-2}\log n)$ with probability

\geqslant 1-\exp\left(-\Omega(|\mathcal{H}^{\prime}|/n)\right)=1-\exp\left(-% \Omega(\varepsilon^{-2}\log n)\right)\geqslant 1-1/\mathrm{poly}(n).

By another Chernoff bound, the probability that $\geqslant\frac{1}{2}$ fraction of $\mathcal{H}^{\langle i\rangle}$ is good is

\geqslant 1-\exp(-\Omega(\varepsilon^{2}|\mathcal{H}^{\langle i\rangle}|))% \geqslant 1-\exp(-\Omega(\log n))\geqslant 1-1/\mathrm{poly}(n),

as desired.

It remains to handle the case when $k$ is even and $\mathrm{corr}(-\widehat{x},x^{*})\geqslant 1-\delta$ . Let us make the following simple observation: since $k$ is even, the distributions $\mathsf{LPN}_{k}(x^{*},m,\varepsilon)$ and $\mathsf{LPN}_{k}(-x^{*},m,\varepsilon)$ are identical. Hence, we can follow the above analysis using $-x^{*}$ as the planted assignment since $\mathrm{corr}(\widehat{x},-x^{*})\geqslant 1-\delta$ , and the aforementioned argument implies that we recover $-x^{*}$ with probability at least $1-1/\mathrm{poly}(n)$ , which finishes the proof. $\hfill\blacktriangleleft$

References

[1] Jackson Abascal, Venkatesan Guruswami, and Pravesh K. Kothari. Strongly refuting all semi-random Boolean CSPs. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 454–472. SIAM, 2021. doi:10.1137/1.9781611976465.28.
[2] Michael Alekhnovich. More on average case vs approximation complexity. In 44th Annual IEEE Symposium on Foundations of Computer Science, 11-14 October 2003, Cambridge, MA, USA. IEEE, 2003.
[3] Sarah R. Allen, Ryan O’Donnell, and David Witmer. How to Refute a Random CSP. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 689–708. IEEE Computer Society, 2015. doi:10.1109/FOCS.2015.48.
[4] Benny Applebaum. Cryptographic Hardness of Random Local Functions: Survey. Computational complexity, 25:667–722, 2016. doi:10.1007/s00037-015-0121-8.
[5] Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 171–180. ACM, 2010. doi:10.1145/1806689.1806715.
[6] Sanjeev Arora, David R. Karger, and Marek Karpinski. Polynomial time approximation schemes for dense instances of NP-hard problems. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA, pages 284–293. ACM, 1995. doi:10.1145/225058.225140.
[7] Boaz Barak, Siu On Chan, and Pravesh K. Kothari. Sum of Squares Lower Bounds from Pairwise Independence. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 97–106. ACM, 2015. doi:10.1145/2746539.2746625.
[8] Boaz Barak and Ankur Moitra. Noisy Tensor Completion via the Sum-of-Squares Hierarchy. In Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, volume 49 of JMLR Workshop and Conference Proceedings, pages 417–445. JMLR.org, 2016. URL: http://proceedings.mlr.press/v49/barak16.html.
[9] Boaz Barak and David Steurer. Proofs, beliefs, and algorithms through the lens of sum-of-squares, 2016. Lecture notes in preparation, available on http://sumofsquares.org.
[10] Wolfgang Barthel, Alexander K Hartmann, Michele Leone, Federico Ricci-Tersenghi, Martin Weigt, and Riccardo Zecchina. Hiding solutions in random satisfiability problems: A statistical mechanics approach. Physical review letters, 88(18):188701, 2002.
[11] Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani. SDP gaps from pairwise independence. Theory of Computing, 8(1):269–289, 2012. doi:10.4086/toc.2012.v008a012.
[12] Andrej Bogdanov and Youming Qiao. On the security of Goldreich’s one-way function. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 12th International Workshop, APPROX 2009, pages 392–405. Springer, 2009. doi:10.1007/978-3-642-03685-9_30.
[13] Xue Chen, Wenxuan Shu, and Zhaienhe Zhou. Algorithms for Sparse LPN and LSPN Against Low-noise. In 38th Annual Conference on Learning Theory (COLT 2025). Association for Computational Learning (ACL), 2025.
[14] Amin Coja-Oghlan, Colin Cooper, and Alan Frieze. An efficient sparse regularity concept. SIAM Journal on Discrete Mathematics, 23(4):2000–2034, 2010. doi:10.1137/080730160.
[15] Amin Coja-Oghlan, Andreas Goerdt, and André Lanka. Strong refutation heuristics for random $k$ -SAT. Combinatorics, Probability & Computing, 16(1):5, 2007.
[16] Uriel Feige. Relations between average case complexity and approximation complexity. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 534–543, 2002. doi:10.1145/509907.509985.
[17] Vitaly Feldman, Will Perkins, and Santosh S. Vempala. Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP’s. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 2836–2844, 2015. URL: https://proceedings.neurips.cc/paper/2015/hash/9597353e41e6957b5e7aa79214fcb256-Abstract.html.
[18] Vitaly Feldman, Will Perkins, and Santosh S. Vempala. On the Complexity of Random Satisfiability Problems with Planted Solutions. SIAM Journal on Computing, 47(4):1294–1338, 2018. doi:10.1137/16M1078471.
[19] Noah Fleming, Pravesh Kothari, and Toniann Pitassi. Semialgebraic Proofs and Efficient Algorithm Design. Foundations and Trends® in Theoretical Computer Science, 14(1-2):1–221, 2019. doi:10.1561/0400000086.
[20] Dimitris Fotakis, Michael Lampis, and Vangelis Th. Paschos. Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, volume 47 of LIPIcs, pages 37:1–37:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPIcs.STACS.2016.37.
[21] Andreas Goerdt and André Lanka. Recognizing more random unsatisfiable 3-sat instances efficiently. Electron. Notes Discret. Math., 16:21–46, 2003. doi:10.1016/S1571-0653(04)00461-5.
[22] Oded Goldreich. Candidate One-Way Functions Based on Expander Graphs. Electron. Colloquium Comput. Complex., 2000. URL: https://eccc.weizmann.ac.il/eccc-reports/2000/TR00-090/index.html.
[23] Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, and Peter Manohar. Efficient algorithms for semirandom planted csps at the refutation threshold. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 307–327. IEEE, 2023. doi:10.1109/FOCS57990.2023.00026.
[24] Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar. Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random. In STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 678–689. ACM, 2022. doi:10.1145/3519935.3519955.
[25] Johan Håstad. Some optimal inapproximability results. Journal of the ACM (JACM), 48(4):798–859, 2001. doi:10.1145/502090.502098.
[26] Samuel B. Hopkins, Jonathan Shi, and David Steurer. Tensor principal component analysis via sum-of-square proofs. In Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 956–1006, Paris, France, 03–06 July 2015. PMLR. URL: https://proceedings.mlr.press/v40/Hopkins15.html.
[27] Jun-Ting Hsieh, Pravesh K. Kothari, and Sidhanth Mohanty. A simple and sharper proof of the hypergraph Moore bound. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 2324–2344. SIAM, 2023. doi:10.1137/1.9781611977554.ch89.
[28] Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367–375, 2001. doi:10.1006/jcss.2000.1727.
[29] Haixia Jia, Cristopher Moore, and Doug Strain. Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively. Journal of Artificial Intelligence Research, 28:107–118, 2007. doi:10.1613/jair.2039.
[30] Pravesh K. Kothari, Ryuhei Mori, Ryan O’Donnell, and David Witmer. Sum of squares lower bounds for refuting any CSP. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 132–145. ACM, 2017. doi:10.1145/3055399.3055485.
[31] Colin McDiarmid. On the method of bounded differences. In Surveys in combinatorics, 1989 (Norwich, 1989), volume 141 of London Math. Soc. Lecture Note Ser., pages 148–188. Cambridge Univ. Press, Cambridge, 1989.
[32] Ryuhei Mori and David Witmer. Lower Bounds for CSP Refutation by SDP Hierarchies. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Paris, France, volume 60 of LIPIcs, pages 41:1–41:30, 2016. doi:10.4230/LIPIcs.APPROX-RANDOM.2016.41.
[33] Ryan O’Donnell and David Witmer. Goldreich’s PRG: evidence for near-optimal polynomial stretch. In 2014 IEEE 29th Conference on Computational Complexity (CCC), pages 1–12. IEEE, 2014. doi:10.1109/CCC.2014.9.
[34] Prasad Raghavendra, Satish Rao, and Tselil Schramm. Strongly refuting random CSPs below the spectral threshold. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 121–131. ACM, 2017. doi:10.1145/3055399.3055417.
[35] Alexander S. Wein, Ahmed El Alaoui, and Cristopher Moore. The Kikuchi Hierarchy and Tensor PCA. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1446–1468. IEEE Computer Society, 2019. doi:10.1109/FOCS.2019.000-2.

[bib.bib1] [1] Jackson Abascal, Venkatesan Guruswami, and Pravesh K. Kothari. Strongly refuting all semi-random Boolean CSPs. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 454–472. SIAM, 2021. doi:10.1137/1.9781611976465.28.

[bib.bib2] [2] Michael Alekhnovich. More on average case vs approximation complexity. In 44th Annual IEEE Symposium on Foundations of Computer Science, 11-14 October 2003, Cambridge, MA, USA. IEEE, 2003.

[bib.bib3] [3] Sarah R. Allen, Ryan O’Donnell, and David Witmer. How to Refute a Random CSP. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 689–708. IEEE Computer Society, 2015. doi:10.1109/FOCS.2015.48.

[bib.bib4] [4] Benny Applebaum. Cryptographic Hardness of Random Local Functions: Survey. Computational complexity, 25:667–722, 2016. doi:10.1007/s00037-015-0121-8.

[bib.bib5] [5] Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 171–180. ACM, 2010. doi:10.1145/1806689.1806715.

[bib.bib6] [6] Sanjeev Arora, David R. Karger, and Marek Karpinski. Polynomial time approximation schemes for dense instances of NP-hard problems. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA, pages 284–293. ACM, 1995. doi:10.1145/225058.225140.

[bib.bib7] [7] Boaz Barak, Siu On Chan, and Pravesh K. Kothari. Sum of Squares Lower Bounds from Pairwise Independence. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 97–106. ACM, 2015. doi:10.1145/2746539.2746625.

[bib.bib8] [8] Boaz Barak and Ankur Moitra. Noisy Tensor Completion via the Sum-of-Squares Hierarchy. In Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, volume 49 of JMLR Workshop and Conference Proceedings, pages 417–445. JMLR.org, 2016. URL: http://proceedings.mlr.press/v49/barak16.html.

[bib.bib9] [9] Boaz Barak and David Steurer. Proofs, beliefs, and algorithms through the lens of sum-of-squares, 2016. Lecture notes in preparation, available on http://sumofsquares.org.

[bib.bib10] [10] Wolfgang Barthel, Alexander K Hartmann, Michele Leone, Federico Ricci-Tersenghi, Martin Weigt, and Riccardo Zecchina. Hiding solutions in random satisfiability problems: A statistical mechanics approach. Physical review letters, 88(18):188701, 2002.

[bib.bib11] [11] Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani. SDP gaps from pairwise independence. Theory of Computing, 8(1):269–289, 2012. doi:10.4086/toc.2012.v008a012.

[bib.bib12] [12] Andrej Bogdanov and Youming Qiao. On the security of Goldreich’s one-way function. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 12th International Workshop, APPROX 2009, pages 392–405. Springer, 2009. doi:10.1007/978-3-642-03685-9_30.

[bib.bib13] [13] Xue Chen, Wenxuan Shu, and Zhaienhe Zhou. Algorithms for Sparse LPN and LSPN Against Low-noise. In 38th Annual Conference on Learning Theory (COLT 2025). Association for Computational Learning (ACL), 2025.

[bib.bib14] [14] Amin Coja-Oghlan, Colin Cooper, and Alan Frieze. An efficient sparse regularity concept. SIAM Journal on Discrete Mathematics, 23(4):2000–2034, 2010. doi:10.1137/080730160.

[bib.bib15] [15] Amin Coja-Oghlan, Andreas Goerdt, and André Lanka. Strong refutation heuristics for random $k$ -SAT. Combinatorics, Probability & Computing, 16(1):5, 2007.

[bib.bib16] [16] Uriel Feige. Relations between average case complexity and approximation complexity. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 534–543, 2002. doi:10.1145/509907.509985.

[bib.bib17] [17] Vitaly Feldman, Will Perkins, and Santosh S. Vempala. Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP’s. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 2836–2844, 2015. URL: https://proceedings.neurips.cc/paper/2015/hash/9597353e41e6957b5e7aa79214fcb256-Abstract.html.

[bib.bib18] [18] Vitaly Feldman, Will Perkins, and Santosh S. Vempala. On the Complexity of Random Satisfiability Problems with Planted Solutions. SIAM Journal on Computing, 47(4):1294–1338, 2018. doi:10.1137/16M1078471.

[bib.bib19] [19] Noah Fleming, Pravesh Kothari, and Toniann Pitassi. Semialgebraic Proofs and Efficient Algorithm Design. Foundations and Trends® in Theoretical Computer Science, 14(1-2):1–221, 2019. doi:10.1561/0400000086.

[bib.bib20] [20] Dimitris Fotakis, Michael Lampis, and Vangelis Th. Paschos. Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, volume 47 of LIPIcs, pages 37:1–37:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPIcs.STACS.2016.37.

[bib.bib21] [21] Andreas Goerdt and André Lanka. Recognizing more random unsatisfiable 3-sat instances efficiently. Electron. Notes Discret. Math., 16:21–46, 2003. doi:10.1016/S1571-0653(04)00461-5.

[bib.bib22] [22] Oded Goldreich. Candidate One-Way Functions Based on Expander Graphs. Electron. Colloquium Comput. Complex., 2000. URL: https://eccc.weizmann.ac.il/eccc-reports/2000/TR00-090/index.html.

[bib.bib23] [23] Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, and Peter Manohar. Efficient algorithms for semirandom planted csps at the refutation threshold. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 307–327. IEEE, 2023. doi:10.1109/FOCS57990.2023.00026.

[bib.bib24] [24] Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar. Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random. In STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 678–689. ACM, 2022. doi:10.1145/3519935.3519955.

[bib.bib25] [25] Johan Håstad. Some optimal inapproximability results. Journal of the ACM (JACM), 48(4):798–859, 2001. doi:10.1145/502090.502098.

[bib.bib26] [26] Samuel B. Hopkins, Jonathan Shi, and David Steurer. Tensor principal component analysis via sum-of-square proofs. In Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 956–1006, Paris, France, 03–06 July 2015. PMLR. URL: https://proceedings.mlr.press/v40/Hopkins15.html.

[bib.bib27] [27] Jun-Ting Hsieh, Pravesh K. Kothari, and Sidhanth Mohanty. A simple and sharper proof of the hypergraph Moore bound. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 2324–2344. SIAM, 2023. doi:10.1137/1.9781611977554.ch89.

[bib.bib28] [28] Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367–375, 2001. doi:10.1006/jcss.2000.1727.

[bib.bib29] [29] Haixia Jia, Cristopher Moore, and Doug Strain. Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively. Journal of Artificial Intelligence Research, 28:107–118, 2007. doi:10.1613/jair.2039.

[bib.bib30] [30] Pravesh K. Kothari, Ryuhei Mori, Ryan O’Donnell, and David Witmer. Sum of squares lower bounds for refuting any CSP. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 132–145. ACM, 2017. doi:10.1145/3055399.3055485.

[bib.bib31] [31] Colin McDiarmid. On the method of bounded differences. In Surveys in combinatorics, 1989 (Norwich, 1989), volume 141 of London Math. Soc. Lecture Note Ser., pages 148–188. Cambridge Univ. Press, Cambridge, 1989.

[bib.bib32] [32] Ryuhei Mori and David Witmer. Lower Bounds for CSP Refutation by SDP Hierarchies. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Paris, France, volume 60 of LIPIcs, pages 41:1–41:30, 2016. doi:10.4230/LIPIcs.APPROX-RANDOM.2016.41.

[bib.bib33] [33] Ryan O’Donnell and David Witmer. Goldreich’s PRG: evidence for near-optimal polynomial stretch. In 2014 IEEE 29th Conference on Computational Complexity (CCC), pages 1–12. IEEE, 2014. doi:10.1109/CCC.2014.9.

[bib.bib34] [34] Prasad Raghavendra, Satish Rao, and Tselil Schramm. Strongly refuting random CSPs below the spectral threshold. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 121–131. ACM, 2017. doi:10.1145/3055399.3055417.

[bib.bib35] [35] Alexander S. Wein, Ahmed El Alaoui, and Cristopher Moore. The Kikuchi Hierarchy and Tensor PCA. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1446–1468. IEEE Computer Society, 2019. doi:10.1109/FOCS.2019.000-2.

Solving Random Planted CSPs Below the nk/2 Threshold

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Our results

Definition 1 (k-ary Boolean CSPs).

Definition 2 (Random planted k-ary Boolean CSPs).

Definition 3 (Distribution Complexity).

Theorem 4.

Noisy 𝒌-XOR / 𝒌-sparse LPN

Definition 5 (Noisy k-XOR / k-sparse LPN instance).

Theorem 6 (Algorithm for Noisy k-XOR).

2 Proof Overview

2.1 Certificates of uniqueness: the algorithm of [23]

The barrier to the approach of [23]: weak expansion of Kikuchi graphs

Definition 7.

2.2 A two part rounding procedure: our approach

Finding an approximate solution

Rounding an approximate solution to an exact solution

3 Preliminaries

Proposition 8.

Proposition 9.

Fact 10 (McDiarmid’s Inequality, [31]).

3.1 Background on the Sum-of-Squares hierarchy

Definition 11 (Pseudo-expectations over the hypercube).

Fact 12.

Fact 13 (SoS Algorithm (Corollary 3.40 in [19])).

Fact 14.

3.2 Sum-of-Squares refutation of 𝒌-XOR

Fact 15 (Refuting k-XOR Systems).

▶ Remark 16.

Corollary 17.

3.3 CSP to 𝒌-XOR reduction

Proposition 18.

Fact 19 (Claim 4.2, [23]).

4 From Planted CSPs to Noisy 𝒌-XOR

Proof of Theorem 4 from Theorem 6.

5 Solving Noisy 𝒌-XOR

Lemma 20 (Finding an approximate solution).

Lemma 21 (Rounding an approximate solution to an exact solution).

Proof of Theorem 6 from Lemmas 20 and 21.

▶ Remark 22.

5.1 Finding an approximate solution: proof of Lemma 20

Lemma 23.

Proof.

Bounding term (𝐈).

Lemma 24.

Bounding term (𝐈𝐈).

Proof of Lemma 20.

5.2 Rounding approximate solutions: proof of Lemma 21

Proof.

References

Solving Random Planted CSPs Below the $n^{k/2}$ Threshold

Definition 1 ( $k$ -ary Boolean CSPs).

Definition 2 (Random planted $k$ -ary Boolean CSPs).

Noisy $𝒌$ -XOR / $𝒌$ -sparse LPN

Definition 5 (Noisy $k$ -XOR / $k$ -sparse LPN instance).

Theorem 6 (Algorithm for Noisy $k$ -XOR).

3.2 Sum-of-Squares refutation of $𝒌$ -XOR

Fact 15 (Refuting $k$ -XOR Systems).

$\blacktriangleright$ Remark 16.

3.3 CSP to $𝒌$ -XOR reduction

4 From Planted CSPs to Noisy $𝒌$ -XOR

5 Solving Noisy $𝒌$ -XOR

$\blacktriangleright$ Remark 22.

Bounding term $(\operatorname{I})$ .

Bounding term $(\operatorname{II})$ .