How to refute a random CSP

On refutation of random CSPs

Constraint satisfaction problems (CSPs) play a major role in computer science. There is a vast theory [BJK05] of how algebraic properties of a CSP predicate affect its worst-case satisfiability complexity; there is a similarly vast theory [Rag09] of worst-case approximability of CSPs. Finally, there is a rich range of research — from the fields of computer science, mathematics, and physics — on the average-case complexity of random CSPs; see [Ach09] for a survey just of random $k$-SAT. This paper is concerned with random CSPs, and in particular the problem of efficiently refuting satisfiability for random instances. This is a well-studied algorithmic task with connections to, e.g., proof complexity [BB02], inapproximability [Fei02], SAT-solvers [SAT], cryptography [ABW10], learning theory [DLSS14], statistical physics [CLP02], and complexity theory [BKS13].

Historically, random CSPs are probably best studied in the case of $k$-SAT, $k\geq 3$. The model here involves choosing a CNF formula $\mathcal{I}$ over $n$ variables by drawing $m$ clauses (ORs of $k$ literals) independently and uniformly at random. (The precise details of the random model are inessential; see Section 3.1 for more information.) This is one of the best known efficient ways of generating hard-seeming instances of $\mathsf{NP}$-complete and $\mathsf{coNP}$-complete problems. The computational hardness depends crucially on the density, $\alpha=m/n$. For each $k$ there is (conjecturally) a constant critical density $\alpha_{k}$ such that $\mathcal{I}$ is satisfiable with high probability when $\alpha<\alpha_{k}$, and $\mathcal{I}$ is unsatisfiable with high probability when $\alpha>\alpha_{k}$. (Here and throughout, “with high probability (whp)” means with probability $1-o(1)$ as $n\to\infty$.) This phenomenon occurs for all nontrivial random CSPs; in the case of $k$-SAT it’s been rigorously proven [DSS15] for sufficiently large $k$.

There is a natural algorithmic task associated with each of the two regimes. When $\alpha<\alpha_{k}$ one wants to find a satisfying assignment for $\mathcal{I}$. When $\alpha>\alpha_{k}$ one wants to refute $\mathcal{I}$; i.e., find a certificate of unsatisfiability. Most heuristic SAT-solvers use DPLL-based algorithms; on unsatisfiable instances, they produce certificates that can be viewed as refutations within the Resolution proof system. More generally, a refutation algorithm for density $\alpha$ is any algorithm that: a) outputs “unsatisfiable” or “fail”; b) never incorrectly outputs “unsatisfiable”; c) outputs “fail” with low probability (i.e., probability $o(1)$). We caution the reader that in this paper we do not consider the related, but distinct, scenario of distinguishing planted random instances from truly random ones. Empirical work suggests that as $\alpha$ increases towards $\alpha_{k}$, finding satisfying assignments becomes more difficult; and conversely, as $\alpha$ increases beyond $\alpha_{k}$, finding certificates of unsatisfiability gradually becomes easier.

The special case of random $3$-XOR has proved particularly important: it is related to $3$-SAT refutation through Feige’s “3XOR Principle” (see [Fei02, FO05, FKO06]); it’s the basis for cryptographic schemes due to Alekhnovich [Ale03] (and is related to the “Learning Parities with Noise” problem); it’s used in the best known lower bounds for the SOS SDP hierarchy [Gri01, Sch08], which we discuss further in Section 6; and, Barak and Moitra [BM15] have shown it to be equivalent to a certain “tensor prediction problem” in learning theory.

Our results and techniques

Here we describe our main results and techniques at a high level. Precise theorem statements appear later in the work and the definitions of the terminology we use is given in Section 3. We also mention that in Section B we will generalize all of our results to the case of larger alphabets; but we’ll just discuss Boolean predicates $P:\{0,1\}^{k}\to\{0,1\}$ for simplicity.

The proof of Theorem 2.1 follows ideas from [COGL07] and earlier works on “discrepancy” of random $k$-SAT instances. The case of even $k$ is notably easier, and we present two “folklore” arguments for it. The case of odd $k$ is trickier. Roughly speaking we view the instance as a homogeneous degree-$k$ multilinear polynomial, which we want to certify takes on only small values on inputs in $\{-1,1\}^{n}$. Considering separately the contributions based on the “last” of the $k$ variables in each constraint, and then using Cauchy–Schwarz, it suffices to bound the norm of a carefully designed quadratic form of dimension $n^{k-1}$, indexed by tuples of $k-1$ variables. This is done using the trace method [Wig55, FK81]. Similar techniques, including the use of the trace method, date back to the 2001 Friedgman–Goerdt work [FG01] refuting random $3$-SAT given $m=n^{3/2+\epsilon}$ constraints.

With Theorem 2.1 in hand, the next step is certifying quasirandomness of random $k$-ary CSP instances having m\geq\mathchoice{\hbox{\displaystyle\widetilde{O}}}{\hbox{\textstyle\widetilde{O}}}{\hbox{\scriptstyle\widetilde{O}}}{\hbox{\scriptscriptstyle\widetilde{O}}}(n^{k/2}) constraints. Roughly speaking we say that a CSP instance is quasirandom if, for every assignment $x\in\{0,1\}^{n}$, the $m$ induced $k$-tuples of literal values are close to being uniformly distributed over $\{0,1\}^{k}$. (Note that this is only a property of the instances’ constraint scopes/negations, and has nothing to do with $P$.) Since the “Vazirani XOR Lemma” implies that a distribution on $\{-1,1\}^{k}$ is uniform if and only if all its $2^{k}$ XORs are have bias $\frac{1}{2}$, we are able to leverage Theorem 2.1 to prove:

If an instance is quasirandom, then no solution can be much better than a randomly chosen one. Thus by certifying quasirandomness we are able to strongly refute random instances of any CSP$(P)$:

In particular, this theorem improves upon [COCF10] by a factor of $\sqrt{n}$ whenever $k$ is odd; this savings is new even in the well-studied case of $k$-SAT.

We remark that property of a predicate $P$ supporting a pairwise uniform distribution has played an important role in approximability theory for CSPs, ever since Austrin and Mossel [AM09] showed that such predicates are hereditarily approximation-resistant under the UGC. Also, note that the largest $t$ for which a predicate $P$ supports a $t$-wise uniform distribution determines the minimum number of constraints required by our algorithm. This value is closely related to the notion of distribution complexity studied by Feldman, Perkins, and Vempala [FPV14, FPV15] in the context of planted random CSPs. Informally, the distribution complexity of a planted CSP is the largest $t$ for which the distribution over constraint inputs $\{-1,1\}^{k}$ induced by the planted assignment is $t$-wise uniform. Despite this similarity, the algorithmic techniques used by Feldman, Perkins, and Vempala in the planted case [FPV14] do not seem to directly apply to refutation.

The idea behind the proof of Theorem 2.4 is that with \mathchoice{\hbox{\displaystyle\widetilde{O}}}{\hbox{\textstyle\widetilde{O}}}{\hbox{\scriptstyle\widetilde{O}}}{\hbox{\scriptscriptstyle\widetilde{O}}}(n^{t/2}) constraints we can use the algorithm of Theorem 2.2 to certify quasirandomness (closeness to uniformity) for all subsets of $t$ out of $k$ coordinates. Thus for every assignment $x\in\{0,1\}^{n}$, the induced distribution on constraint $k$-tuples is ($o(1)$-close to) $t$-wise uniform. Since $P$ does not support a $t$-wise uniform distribution, this essentially shows that no $x$ can induce a fully-satisfying distribution on constraint inputs. To handle the $o(1)$-closeness caveat, we show that if $P$ does not support a $t$-wise uniform distribution, then it is $\delta$-far from supporting such a distribution, for $\delta=\Omega_{k}(1)$. The algorithm can then in fact $(\delta-o(1))$-refute random CSP$(P)$ instances.

To briefly illustrate the result, consider the Exactly-$k$-out-of-$2k$-SAT CSP, studied previously in [BB02, GJ03]. The associated predicate supports a $1$-wise uniform distribution, namely the uniform distribution over strings in $\{0,1\}^{2k}$ of Hamming weight $k$. However, it is not hard to show that it does not support any pairwise uniform distribution. As a consequence, random instances of this CSP can be refuted with only \mathchoice{\hbox{\displaystyle\widetilde{O}}}{\hbox{\textstyle\widetilde{O}}}{\hbox{\scriptstyle\widetilde{O}}}{\hbox{\scriptscriptstyle\widetilde{O}}}(n) constraints, independent of $k$.

Recently, an exciting approach to proving hardness-of-learning results has been developed by Daniely, Linial, and Shalev-Shwartz [DLSS13, DLSS14, DSS14, Dan15]. The most general results appear in [DLSS14]. In this work, Daniely et al. prove computational hardness of several central learning theory problems, based on two assumptions concerning the hardness of random CSP refutation. While the assumptions made in [DSS14, Dan15] appear to be plausible, our work unfortunately shows that the more general assumptions made in [DLSS14] are false.

In [DLSS14] it is shown how to obtain three very notable hardness-of-learning results from these assumptions. However as stated, our work falsifies the SRCSP Assumptions. Indeed, the assumptions are false even in the three specific cases used by [DLSS14] to obtain hardness-of-learning results. We now describe these cases.

The Huang predicates $(H_{\kappa})$ are arity-$\Theta(\kappa^{3})$ predicates introduced in [Hua13]; they are hereditarily approximation resistant on satisfiable instances and have $0$-variability $\Omega(\kappa)$. In [DLSS14] they are used in SRCSP Assumption 1 to deduce hardness of PAC-learning DNFs with $\omega(1)$ terms. However:

For all $\kappa\geq 9$, the predicate $H_{\kappa}$ does not support a $4$-wise uniform distribution.

Thus by Theorem 2.4 we can efficiently refute random instances of CSP($H_{\kappa}$) with just \mathchoice{\hbox{\displaystyle\widetilde{O}}}{\hbox{\textstyle\widetilde{O}}}{\hbox{\scriptstyle\widetilde{O}}}{\hbox{\scriptscriptstyle\widetilde{O}}}(n^{2}) constraints, independent of $\kappa$. This contradicts SRCSP Assumption 1.

Finally, we also prove that SRCSP Assumption 1 is false for another family of predicates $(T_{k})$ used by [DLSS14] to show hardness of PAC-learning intersections of $4$ Boolean halfspaces.

Our results described in these three cases all use linear programming duality. Specifically, in Lemma 3.16 we show that $P$ is $\delta$-far from supporting a $t$-wise uniform distribution if and only if there exists a $k$-variable multilinear polynomial $Q$ that satisfies certain properties involving $P$ and $\delta$. We then explicitly construct these dual polynomials for the Huang, Majority, and $T_{k}$ predicates.

We conclude this section by emphasizing the importance of the Daniely–Linial–Shalev-Shwartz hardness-of-learning program, despite the above results. Indeed, subsequently to [DLSS14], Daniely and Shalev-Shwartz [DSS14] showed hardness of improperly learning DNF formulas with $\omega(\log n)$ terms under a much weaker assumption than SRCSP Assumption $1$. Specifically, their work only assumes that for all $d$ there is a large enough $k$ such that refuting random $k$-SAT instances is hard when there are $m=n^{d}$ constraints. This assumption looks quite plausible to us, and may even be true with $k$ not much larger than $2d$. Most recently, Daniely showed hardness of approximately agnostically learning halfspaces using the XOR predicate rather than majority [Dan15]. This result shows that there is no efficient algorithm that agnostically learns halfspaces to within a constant approximation ratio under the assumption that refuting random $k$-XOR instances is hard when $m=n^{c\sqrt{k}\log k}$ for some $c>0$. He also shows hardness of learning halfspaces to within an approximation factor of $2^{\log^{1-\nu}n}$ for any $\nu>0$ assuming that there exists some constant $c>0$ such that for all $s$, refuting random $k$-XOR instances with $k=\log^{s}n$ is hard when $m=n^{ck}$.

2 Evidence for the optimality of our results

It’s natural to ask whether the $n^{t/2}$ dependence in our main Theorem 2.4 can be improved. As we don’t expect to prove unconditional hardness results, we instead merely seek good evidence that refuting $(t-1)$-wise supporting predicates $P$ is hard when $m\ll n^{t/2}$. A natural form of evidence would be showing that various strong classes of polynomial-time refutation algorithms fail when $m\ll n^{t/2}$. To make sense of this we need to talk about the form of such algorithms; i.e., propositional proof systems.

Recently, there has been significant study of the “SOS” (Sum-Of-Squares) proof system, introduced by Grigoriev and Vorobjov [GV01]; see, e.g., [OZ13, BS14] for discussion. It has the following virtues: a) it is very powerful, being able to efficiently simulate other proof systems (e.g., Resolution, Lovász–Schrijver); b) it is automatizable [Las00, Par00], meaning that $n$-variable “degree-$d$ SOS proofs” can be found in $n^{O(d)}$ time whenever they exist; c) we do know some examples of lower bounds for degree-$d$ SOS proofs. In Section 6 of this paper we show the following:

All of our refutation algorithms for $k$-ary predicates can be extended to produce degree-$2k$ SOS proofs.

We now return to the question of evidence for the optimality of constraint density used in our results. Dating back to Franco–Paull [FP83] and Chvátal–Szemerédi [CS88], there has been a long line of work in proof complexity showing lower bounds for refuting random $3$-SAT instances, especially in the Resolution proof system. This culminated in the work of Ben-Sasson and Wigderson [BSW99], which showed that for random $3$-SAT (and $3$-XOR) with $m=O(n^{3/2-\epsilon})$, Resolution refutations require size $2^{n^{\Omega(\epsilon)}}$ (whp). More recently, Schoenebeck [Sch08] showed (using the expansion analysis of [BSW99]) that random $k$-XOR and $k$-SAT instances with $m\leq n^{k/2-\epsilon}$ require SOS proofs of degree $n^{\Omega(\epsilon)}$, and hence take $2^{n^{\Omega(\epsilon)}}$ time to refute by the “SOS Method”. See [Tul09, Cha13] for related larger-alphabet followups. These results show that the Barak–Moitra \mathchoice{\hbox{\displaystyle\widetilde{O}}}{\hbox{\textstyle\widetilde{O}}}{\hbox{\scriptstyle\widetilde{O}}}{\hbox{\scriptscriptstyle\widetilde{O}}}(n^{k/2}) bound for refuting random $k$-XOR (which also works in $O(k)$-degree SOS) and our bound for random $k$-SAT are tight (up to subpolynomial factors) within the SOS framework. Given the power of the SOS framework, this arguably constitutes some reasonable evidence that no polynomial-time algorithm can refute random $k$-SAT instances with $m\ll n^{k/2}$.

We now discuss our main theorem’s $n^{t/2}$ bound for predicates $P$ not supporting $t$-wise uniform distributions. Suppose $P$ is a predicate that does support a $(t-1)$-wise uniform distribution, where $t>2$. In the context of inapproximability and SDP-hierarchy integrality gaps, this condition on $P$ has been significantly studied in the case of $t=3$. For $P$ supporting pairwise uniformity, it is known [BGMT12, TW13] that the Sherali–Adams and Lovász–Schrijver+ SDP hierarchies require degree $\Omega(n)$ to refute random CSP$(P)$ instances (whp) when $m=O(n)$. This result was also recently proven for the stronger SOS proof system by Barak, Chan, and Kothari [BCK15], except that the CSP$(P)$ instances are not quite uniformly random; they are “slightly pruned” random instances. For any $t>2$, the second and third authors recently essentially showed [OW14] that for the Sherali–Adams+ SDP hierarchy, degree $n^{\Omega(\epsilon)}$ is (whp) necessary to refute random CSP$(P)$ instances when $m\leq n^{t/2-\epsilon}$. As a caveat, again the instances are slightly pruned random instances, rather than being purely uniformly random. (The instances in [OW14] are also in the “Goldreich [Gol00] style”; i.e., there are no literals, but the “right-hand sides” are random. However it is not hard to show the proofs in [OW14] go through in the standard random model of this paper.) Future work [MWW15] is devoted to removing the pruning in these instances. Although the Sherali–Adams+ SDP hierarchy is certainly weaker than the SOS hierarchy, these works still constitute some evidence that our main theorem’s requirement of m\geq\mathchoice{\hbox{\displaystyle\widetilde{O}}}{\hbox{\textstyle\widetilde{O}}}{\hbox{\scriptstyle\widetilde{O}}}{\hbox{\scriptscriptstyle\widetilde{O}}}(n^{t/2}) for non-$t$-wise supporting predicates may be essentially optimal.

3 Certifying independence number and chromatic number of random hypergraphs

Coja-Oghlan, Goerdt, and Lanka [COGL07] also use their CSP refutation techniques to certify that random $3$- and $4$-uniform hypergraphs have small independence number and large chromatic number. We extend these results to random $k$-uniform hypergraphs.

For a random $k$-uniform hypergraph $H$, there is a polynomial time algorithm certifying that the independence number of $H$ is at most $\beta$ with high probability when $H$ has at least \mathchoice{\hbox{\displaystyle\widetilde{O}}}{\hbox{\textstyle\widetilde{O}}}{\hbox{\scriptstyle\widetilde{O}}}{\hbox{\scriptscriptstyle\widetilde{O}}}\left(\frac{n^{5k/2}}{\beta^{2k}}\right) hyperedges.

For a random $k$-uniform hypergraph $H$, there is a polynomial time algorithm certifying that the chromatic number of $H$ is at least $\xi$ with high probability when $H$ has at least \mathchoice{\hbox{\displaystyle\widetilde{O}}}{\hbox{\textstyle\widetilde{O}}}{\hbox{\scriptstyle\widetilde{O}}}{\hbox{\scriptscriptstyle\widetilde{O}}}\left(\xi^{2k}n^{k/2}\right) hyperedges.

The proofs of these theorems follow the outline of [COGL07]. We show Theorem 2.9 using a slightly more general form of Theorem 2.1. Theorem 2.10 follows almost directly from Theorem 2.9 using the fact that every color class of a valid coloring is an independent set. Details are given in Appendix C.

Preliminaries and notation

We next define a standard random model for CSPs. For $P:\{-1,1\}^{k}\to\{0,1\}$, let $\mathcal{F}_{P}(n,p)$ be the distribution over CSP instances given by including each of the $2^{k}n^{k}$ possible constraints independently with probability $p$. Note that we may include constraints on different permutations of the same set of variables, constraints on the same tuple of variables with different negations $c$, and constraints with the same variable occurring as more than one argument. It is reasonable to include such constraints in the case that the predicate $P$ is not a symmetric function. We use $\overline{m}$ to denote the expected number of constraints, namely $2^{k}n^{k}p$. As noted in Fact 3.6 below, the number of constraints $m$ in a draw from $\mathcal{F}_{P}(n,p)$ is very tightly concentrated around $\overline{m}$, and we often blur the distinction between these parameters. Appendix D explicitly describes a method for simulating an instance drawn from $\mathcal{F}_{P}(n,p)$ when the number of constraints is fixed.

We now introduce an important notion for this paper: that of a CSP instance being quasirandom. Versions of this notion originate in the works of Goerdt and Lanka [GL03] (under the name “discrepancy”), Khot [Kho06] (“quasi-randomness”), Austrin and Håstad [AH13] (“adaptive uselessness”), and Chan [Cha13] (“low correlation”), among other places. To define it, we first need to define the induced distribution of an instance and an assignment.

Here we use the notation $U^{k}$ for the uniform distribution on $\{-1,1\}^{k}$ as well as the following:

An immediate consequence of an instance being quasirandom is that its optimum is close to $\overline{P}$:

We conclude the discussion of CSPs by recording some facts that are proven easily with the Chernoff bound:

Let $\mathcal{I}\sim\mathcal{F}_{P}(n,p)$. Then the following statements hold with high probability.

$m=\left\lvert\mathcal{I}\right\rvert\in\overline{m}\cdot\left(1\pm O\left(\sqrt{\frac{\log n}{\overline{m}}}\right)\right)$.

$\mathcal{I}$ is $O\left(\sqrt{2^{k}\cdot\frac{n}{\overline{m}}}\right)$-quasirandom.

2 Algorithms and refutations on random CSPs

where $p$ is defined by $\overline{m}=2^{k}n^{k}p$. Although $\mathcal{A}$ is often a deterministic algorithm, we do allow it to be randomized, in which case the above probability is also over the “internal random coins” of $\mathcal{A}$.

3 tt-wise uniformity

An important notion for this paper is that of $t$-wise uniformity. Recall:

Probability distribution $\mathcal{D}$ on $\{-1,1\}^{k}$ is said to be $t$-wise uniform, $1\leq t\leq k$, if for all $S\subseteq[k]$ with $|S|=t$ the random variable $x_{S}$ is uniform on $\{-1,1\}^{t}$ when $x\sim\mathcal{D}$. (We remark that this condition is sometimes inaccurately called “$t$-wise independence” in the literature.)

We will also consider the more general notion of $(\epsilon,t)$-wise uniformity. This is typically defined using Fourier coefficients:

Probability distribution $\mathcal{D}$ on $\{-1,1\}^{k}$ is said to be $(\epsilon,t)$-wise uniform if $|\widehat{D}(S)|\leq\epsilon$ for all $S\subseteq[k]$ with $0<|S|\leq t$, where $D=2^{k}\cdot\mathcal{D}$ is the probability density associated with distribution $\mathcal{D}$.

It is a simple fact (and it follows from Lemma 3.13 below) that $(0,t)$-wise uniformity is equivalent to $t$-wise uniformity.

Also important for us is a related but distinct notion, that of being $\epsilon$-close to a $t$-wise uniform distribution. It’s easy to show that if $\mathcal{D}$ is $\epsilon$-close to a $t$-wise uniform distribution then $\mathcal{D}$ is $(2\epsilon,t)$-wise uniform. In the other direction, we have the following (see also [AAK+07] for some quantitative improvement):

(Alon–Goldreich-Mansour [AGM03, Theorem 2.1]). If $\mathcal{D}$ is an $(\epsilon,t)$-wise uniform distribution on $\{-1,1\}^{k}$, then there exists a $t$-wise uniform distribution $\mathcal{D}^{\prime}$ on $\{-1,1\}^{k}$ with

In particular if $t=k$ we have the bound $2^{k}\cdot\epsilon$ (and this can also be improved [Gol11] to $2^{k/2-1}\cdot\epsilon$).

A predicate $P:\{-1,1\}^{k}\to\{0,1\}$ is said to be $t$-wise supporting if there is a $t$-wise uniform distribution $\mathcal{D}$ whose support is contained in $P^{-1}(1)$. We say $P$ is $\delta$-far from $t$-wise supporting if every $t$-wise uniform distribution $\mathcal{D}$ is $\delta$-far from being supported on $P$; i.e., has probability mass at least $\delta$ on $P^{-1}(0)$.

4 A dual characterization of limited uniformity

It is known that the condition of $P$ supporting a $t$-wise uniform distribution is equivalent to the feasibility of a certain linear program; hence one can show that $P$ is not $t$-wise supporting by exhibiting a certain dual object, namely a polynomial. This appears, e.g., in work of Austrin and Håstad [AH09, Theorem 3.1]. Herein we will extend this fact by giving a dual characterization of being far from $t$-wise supporting.

$Q(z)\geq\delta-1\quad\forall z\in\{-1,1\}^{k}$;

$Q(z)\geq\delta\quad\forall z\in P^{-1}(1)$;

$\widehat{Q}(\emptyset)=0$, i.e., $Q$ has no constant coefficient.

We now provide the quantitative version of the aforementioned [AH09, Theorem 3.1]:

Let $P:\{-1,1\}^{k}\rightarrow\{0,1\}$ and let $0<\delta<1$. Then $P$ is $\delta$-far from $t$-wise supporting if and only if there is a $\delta$-separating polynomial for $P$ of degree at most $t$.

The proof is an application of linear programming duality. Consider the following LP, which has variables $\mathcal{D}(z)$ for each $z\in\{-1,1\}^{k}$.

minimize $\displaystyle\sum_{\mathclap{z\in\{-1,1\}^{k}}}(1-$ $\displaystyle P(z))\mathcal{D}(z)$ (1) s.t. $\displaystyle\sum_{\mathclap{z\in\{-1,1\}^{k}}}\mathcal{D}(z)z^{S}=2^{k}\cdot\widehat{\mathcal{D}}(S)$ $\displaystyle=0$ $\displaystyle\forall S\subseteq[k]\quad 0<|S|\leq t$ (2) $\displaystyle\sum_{{z\in\{-1,1\}^{k}}}\mathcal{D}(z)$ $\displaystyle=1$ (3) $\displaystyle\mathcal{D}(z)$ $\displaystyle\geq 0$ $\displaystyle\forall z\in\{-1,1\}^{k}$

Constraint (3) and the nonnegativity constraint ensure that $\mathcal{D}$ is a probability distribution on $\{-1,1\}^{k}$. Constraint (2) expresses that $\mathcal{D}$ is $t$-wise uniform (see Remark 3.12). The objective (1) is minimizing the probability mass that $\mathcal{D}$ puts on assignments in $P^{-1}(0)$. Thus the optimal value of the LP is equal to the smallest $\gamma$ such that $P$ is $\gamma$-close to $t$-wise supporting; equivalently, the largest $\gamma$ such that $P$ is $\gamma$-far from $t$-wise supporting.

The following is the dual of the above LP. It has a variable $c(S)$ for each $0<|S|\leq t$ as well as a variable $\xi$ corresponding to constraint (3).

maximize $\displaystyle\xi$ (4) s.t. $\displaystyle\sum_{\begin{subarray}{c}S\subseteq[k]\\ 0<|S|\leq t\end{subarray}}c(S)z^{S}$ $\displaystyle\leq 1-P(z)-\xi$ $\displaystyle\forall z\in\{-1,1\}^{k}.$ (5)

Observe that a feasible solution $(\{c(S)\}_{S},\xi)$ is precisely equivalent to a multilinear polynomial $Q$ of degree at most $t$, namely $Q(z)=-\sum_{S}c(S)z^{S}$, that $\xi$-separates $P$.

Thus $P$ is $\delta$-far from $t$-wise supporting if and only if the LP’s objective (1) is at least $\delta$, if and only if the dual’s objective (4) is at least $\delta$, if and only if there is a $\delta$-separating polynomial for $P$ of degree at most $t$. ∎

From this proof we can also derive that if $P$ fails to be $t$-wise supporting then it must in fact be $\Omega_{k}(1)$-far from being $t$-wise supporting:

Suppose $P:\{-1,1\}^{k}\to\{0,1\}$ is not $t$-wise supporting. Then it is in fact $\delta$-far from $t$-wise supporting for \delta=2^{-\mathchoice{\hbox{\displaystyle\widetilde{O}}}{\hbox{\textstyle\widetilde{O}}}{\hbox{\scriptstyle\widetilde{O}}}{\hbox{\scriptscriptstyle\widetilde{O}}}(k^{t})} (or \delta=2^{-\mathchoice{\hbox{\displaystyle\widetilde{O}}}{\hbox{\textstyle\widetilde{O}}}{\hbox{\scriptstyle\widetilde{O}}}{\hbox{\scriptscriptstyle\widetilde{O}}}(2^{k})} when $t=k$).

Let $K=1+\sum_{i=1}^{t}\binom{k}{t}$ be the number of variables in the dual LP from Lemma 3.16, so $K\leq k^{t}+1$ in general, with $K\leq 2^{k}$ when $t=k$. By assumption, the objective (4) of the dual LP’s optimal solution is strictly positive. This optimum occurs at a vertex, which is the solution of a linear system given by a $K\times K$ matrix of $\pm 1$ entries and a “right-hand side” vector with $0,1$ entries. By Cramer’s rule, the solution’s entries are ratios of determinants of integer matrices with entries in $\{-1,0,1\}$. Thus any strictly positive entry is at least $1/N$, where $N$ is the maximum possible such determinant. By Hadamard’s inequality, $N=K^{K/2}$ and the claimed result follows. ∎

Quasirandomness and its implications for refutation

For $k\geq 2$ and $p\geq n^{-k/2}$, let $\{w(T)\}_{T\in[n]^{k}}$ be independent random variables such that for each $T\in[n]^{k}$,

Then there is an efficient algorithm certifying that

In this form, the theorem is not really about CSP refutation at all. It says that the value of a polynomial with random coefficients is close to its expectation when its inputs are bounded.

We give the proof in Appendix A. It follows techniques from [COGL07] fairly closely and is essentially the same as the proof of [BM15]. We will use this theorem to prove our results in subsequent sections.

We obtain strong refutation of $k$-XOR as a simple corollary.

so for a $k$-XOR instance \mathcal{I}\sim\mathcal{F}_{\textup{k-XOR}}(n,p),

where $w(T)=-2^{-k}\sum_{c\in\{\pm 1\}^{k}}1_{\{(T,c)\in\mathcal{I}\}}\prod_{i\in[k]}c_{i}$. The $w(T)$’s are random variables depending on the choice of $\mathcal{I}$; observe that $\mathop{\bf E\/}[w(T)]=0$, $\mathop{\bf Pr\/}[w(T)\neq 0]\leq 2^{k}p$, and $\left\lvert w(T)\right\rvert\leq 1$ for all $T\in[n]^{k}$. By Theorem 4.1, there is an algorithm certifying that

with high probability when $p\geq n^{-k/2}$. Since $m=(1+o(1))\overline{m}$ with high probability, choosing $\overline{m}\geq\frac{2^{O(k)}n^{k/2}\log^{3}n}{\gamma^{2}}$ gives the desired result. ∎

2 Quasirandomness and strong refutation of any kk-CSP

Next, we will use the algorithm of Theorem 4.1 to certify that an instance of CSP$(P)$ is quasirandom. This will immediately give us a strong refutation algorithm.

In order to certify quasirandomness, Lemma 3.13 implies that it suffices to certify each Fourier coefficient of $D_{\mathcal{I},x}$ has small magnitude.

Let $\emptyset\neq S\subseteq[k]$ with $|S|=s$. There is an algorithm that, with high probability, certifies that

for all $x\in\{-1,1\}^{n}$, assuming also that $\overline{m}\geq\max\{n^{s/2},n\}$.

To prove this lemma, we need another lemma certifying that polynomials whose coefficients are sums of $0$-mean random variables have small value.

The proof is straightforward and we defer it to Section 4.4.

Without loss of generality, assume $1\in S$. Applying definitions, we see that

where we define $w_{S}(T,c^{\prime})=1_{\{(T,(1,c^{\prime}))\in\mathcal{I}\}}(c^{\prime})^{S\setminus\{1\}}-1_{\{(T,(-1,c^{\prime}))\in\mathcal{I}\}}(c^{\prime})^{S\setminus\{1\}}$ and recall that $T_{S}$ is the projection of $T$ onto the the coordinates in $S$. It is clear that $\mathop{\bf E\/}[w_{S}(T,c^{\prime})]=0$, $\mathop{\bf Pr\/}[w_{S}(T,c^{\prime})\neq 0]\leq p$, and $|w_{S}(T,c^{\prime})|\leq 1$. There are $\tau=2^{k-1}n^{k-s}$ terms in each sum of $w_{S}(T,c^{\prime})$’s and we can apply Lemma 4.4. When $s=2$, we plug in these values and see that we can certify that $\widehat{D_{\mathcal{I},x}}(S)\leq\frac{2^{O(s)}n^{s/4}\log^{5/2}n}{\overline{m}^{1/2}}$. When $s=1$, $\overline{m}\geq n$ implies that $\tau p\geq\frac{1}{2}$ and we can certify that $\widehat{D_{\mathcal{I},x}}(S)\leq\frac{2^{O(s)}\sqrt{n}\log n}{\overline{m}^{1/2}}$. The lower bound can be proved in exactly the same way by considering the random variables $-w_{S}(T,c^{\prime})$. ∎

The existence of an algorithm for certifying quasirandomness follows from Lemmas 3.13 and 4.3.

3 (ϵ,t)(\epsilon,t)-quasirandomness and Ω⁡(1)\Omega(1)-refutation of non-tt-wise-supporting CSPs

In the case that a predicate is not $t$-wise supporting, a weaker notion of quasirandomness suffices to obtain $\Omega(1)$-refutation.

An instance $\mathcal{I}$ of $\textrm{CSP}(P)$ is $(\epsilon,t)$-quasirandom if $\mathcal{D}_{\mathcal{I},x}$ is $(\epsilon,t)$-wise uniform for every $x\in\{-1,1\}^{n}$.

Fact 3.6 shows that random instances with \mathchoice{\hbox{\displaystyle\widetilde{O}}}{\hbox{\textstyle\widetilde{O}}}{\hbox{\scriptstyle\widetilde{O}}}{\hbox{\scriptscriptstyle\widetilde{O}}}(n) constraints are $(o(1),t)$-quasirandom for all $t\leq k$ with high probability. Lemma 4.3 directly implies that we can certify $(\epsilon,t)$-quasirandomness when m\geq\mathchoice{\hbox{\displaystyle\widetilde{O}}}{\hbox{\textstyle\widetilde{O}}}{\hbox{\scriptstyle\widetilde{O}}}{\hbox{\scriptscriptstyle\widetilde{O}}}(n^{t/2}).

There is an efficient algorithm that certifies that an instance $\mathcal{I}\sim\mathcal{F}_{P}(n,p)$ of CSP$(P)$ is $(\gamma,t)$-quasirandom with high probability when $\overline{m}\geq\frac{2^{O(t)}n^{t/2}\log^{5}n}{\gamma^{2}}$ and $t\geq 2$.

We now reach the main result of this section, which states that if a predicate is $\delta$-far from $t$-wise supporting, then we can almost $\delta$-refute instances of CSP$(P)$.

We give two proofs of this theorem. In Proof 1, the theorem follows directly from certification of $(\gamma,t)$-quasirandomness and Lemma 3.13.

Proof 2 gives a slightly weaker version of Theorem 4.9, requiring the stronger assumption that $\overline{m}\geq\frac{2^{O(k)}n^{t/2}\log^{5}n}{\gamma^{2}}$. It is based on the dual polynomial characterization of being $\delta$-far from $t$-wise supporting. While perhaps less intuitive than Proof 1, Proof 2 is more direct. It only uses the XOR refutation algorithm and bypasses [AGM03]’s connection between $(\epsilon,t)$-wise uniformity and $\epsilon$-closeness to a $t$-wise uniform distribution. We were able to convert Proof 2 into an SOS proof (see Section 6.4), but we did not see how to translate Proof 1 into an SOS version. Proof 2 requires Plancherel’s Theorem, a fundamental result in Fourier analysis.

Since $P$ is $\delta$-far from $t$-wise supporting, there exists a degree-$t$ polynomial $Q$ that $\delta$-separates $P$. The definition of $\delta$-separating implies that $P(z)-(1-\delta)\leq Q(z)$ for all $z\in\{-1,1\}^{k}$. Summing over all constraints, we get that for all $x\in\{-1,1\}^{n}$,

It then remains to certify that $\mathop{\bf E\/}_{\boldsymbol{z}\in\mathcal{D}_{\mathcal{I},x}}[Q(\boldsymbol{z})]\leq\gamma$. Observe that

where the second equality follows from Plancherel’s Theorem. Since $Q\geq-1$ and $\mathop{\bf E\/}[Q]=0$, $Q\leq 2^{k}$ and hence $|\widehat{Q}(S)|\leq 2^{k}$ for all $S$. To finish the proof, we apply Lemma 4.3 to certify that $\left|\widehat{D_{\mathcal{I},x}}(S)\right|\leq\frac{\gamma}{2^{2k}}$ for all $S$. ∎

4 Proof of Lemma 4.4

Let $X_{1},\ldots,X_{M}$ be independent $0$-mean random variables such that $\left\lvert X_{i}\right\rvert\leq B$. Then, for $a>0$,

Observe that the $v_{U}$’s are independent and that each one is the sum of $\tau$ mean-$0$, i.i.d. random variables with magnitude at most $1$. Noting that $\sum_{i=1}^{\tau}\mathop{\bf E\/}[w_{U}(i)^{2}]\leq\tau p$, we can use Bernstein’s Inequality to show that the $|v_{U}|$’s are not too big with high probability. If $s\geq 2$, Theorem 4.1 then implies that the desired algorithm exists. If $s=1$, we are simply bounding a linear function over $\pm 1$ variables. We consider two cases: Small $p$ and large $p$.

Choosing $a=2s\log n$ in Bernstein’s Inequality, we see that $\mathop{\bf Pr\/}[|v_{U}|\geq 2s\log n]\leq n^{-2s}$. A union bound over all $U$ then implies that \mathop{\bf Pr\/}[\text{any|v_{U}|>2s\log n}]\leq n^{-s}. If $s\geq 2$, we observe that $\mathop{\bf Pr\/}[v_{U}\neq 0]\leq\tau p$, scale the $v_{U}$’s down by $2s\log n$, and apply Theorem 4.1 to get the stated result. If $s=1$, we obtain the second bound by observing that

We set $a=4s\sqrt{\tau p}\log n$ and get that \mathop{\bf Pr\/}[\text{any\left\lvert v_{U}\right\rvert>4s\sqrt{\tau p}\log n}]\leq n^{-s} as above. If $s\geq 2$, we can then divide the $v_{U}$’s by $4s\sqrt{\tau p}\log n$ and apply Theorem 4.1. If $s=1$, we get a bound of $4\sqrt{\tau p}\cdot n\log n$ in the same way as (10). ∎

Hardness of learning implications

Daniely et al. reduce the problem of distinguishing between random instances of $\textrm{CSP}(P)$ and instances with value at least $\alpha$ as a PAC learning problem by transforming each constraint into a labeled example. To show hardness of improperly learning a certain hypothesis class in the PAC model, they define a predicate $P$ that is specific to the hypothesis class and assume hardness of distinguishing between random instances of $\textrm{CSP}(P)$ and instances with $n^{d}$ constraints and value at least $\alpha$ for all $d>0$. They then demonstrate that the sample can be realized (or approximately realized) by some function in the hypothesis class if the CSP instance is satisfiable (or has value at least $\alpha$). They also show that if the given CSP instance is random, the set of examples will have error at least $\tfrac{1}{4}$ (in the agnostic case $\tfrac{1}{5})$ for all $h$ in the hypothesis class with high probability. Using this approach, they obtain hardness results for the following problems: improperly learning DNF formulas, improperly learning intersections of 4 halfspaces, and improperly approximately agnostically learning halfspaces for any approximation factor.

The hardness assumptions made in [DLSS14] are the same as those presented in Section 2.1, except for a few minor differences. First, their model fixes the number of constraints rather than the probability with which each constraint is included in the instance. It is well-known that results in one model easily translate to the other. We include a proof in Appendix D for completeness. Additionally, SRCSP Assumptions 1 and 2 purport hardness of distinguishing random instances of $\textrm{CSP}(P)$ from satisfiable instances, even when the algorithm is allowed to err with probability $\tfrac{1}{4}$ over its internal coins. The algorithms presented in the preceding sections never err on satisfiable instances; further, they only fail to certify random instances with probability $o(1)$. As a result, our refutation algorithms also falsify weaker versions of both SRCSP Assumptions, wherein the allowed probability of error is both lower and one-sided. For each predicate presented in [DLSS14], we falsify the appropriate SRCSP assumption using the following approach. For each predicate $P$ and corresponding $\delta>0$ , we define a degree-$t$ polynomial that $\delta$-separates $P$. Using the refutation techniques presented in the preceding sections, we deduce that \mathchoice{\hbox{\displaystyle\widetilde{O}}}{\hbox{\textstyle\widetilde{O}}}{\hbox{\scriptstyle\widetilde{O}}}{\hbox{\scriptscriptstyle\widetilde{O}}}(n^{t/2}) constraints are sufficient to distinguish random instances of $\textrm{CSP}(P)$ from those that are satisfiable (or have value at least $\alpha$). In order to simplify the presentation, we begin with simpler versions of the polynomials and then scale them to attain the appropriate values of $\delta$. The following lemma will be of use for this scaling.

Define $\mathcal{Q}(z)=\frac{Q(z)}{\theta_{1}-\theta_{0}}$. Clearly $\mathcal{Q}$ is also unbiased and has degree $t$. Then for all $z\in P_{1}$, $\frac{Q(z)}{\theta_{1}-\theta_{0}}\geq\frac{\theta_{1}}{\theta_{1}-\theta_{0}}$. Similarly, for all $z$, $\frac{Q(z)}{\theta_{1}-\theta_{0}}\geq\frac{\theta_{0}}{\theta_{1}-\theta_{0}}=-\frac{\theta_{1}-\theta_{0}}{\theta_{1}-\theta_{0}}+\frac{\theta_{1}}{\theta_{1}-\theta_{0}}=-1+\frac{\theta_{1}}{\theta_{1}-\theta_{0}}$. ∎

We now demonstrate that the above can be applied to the predicates suggested in [DLSS14] by defining separating polynomials and applying Theorem 4.9

2 Huang’s predicate and hardness of learning DNF formulas

In order to obtain hardness of improperly learning DNF formulas with $\omega(1)$ terms, Daniely et al. use the following predicate, introduced by Huang [Hua13]. Huang showed that it is hereditarily approximation resistant; Daniely et al. also observed that its $0$-variability is $\Omega(k^{1/3})$ [DLSS14].

Daniely et al. reduce the problem of distinguishing between random instances of $\textrm{CSP}(H_{\kappa})$ with $2n^{d}$ constraints and satisfiable instances to the problem of improperly PAC learning the class of DNF formulas with $\omega(1)$ terms on a sample of $O(n^{d})$ training examples with error $\epsilon=1/5$ with probability at least $\tfrac{3}{4}$. Here we show that there exists a polynomial time algorithm that refutes random instances of $\textrm{CSP}(H_{\kappa})$ by demonstrating that $H_{k}$ does not support a 4-wise uniform distribution and applying Theorem 4.9.

As a notational shorthand, write $z_{abc}$ for $z_{\{i_{a},i_{b},i_{c}\}}$. Define $\zeta:[\kappa]^{6}\times\{-1,1\}^{k}\rightarrow$ as follows:

Observe that for each monomial $z_{T_{1}}z_{T_{2}}z_{T_{3}}z_{T_{4}}$ of $\zeta$, for every $j\in$, $\sum_{i=1}^{4}1_{\{T_{i}\ni j\}}=2$. Further, for each $T\subseteq$ with $|T|=3$, $z_{T}$ appears exactly once in $\zeta$. Let $\mathcal{Z}_{6}$ be the set of all ordered 6-tuples of distinct elements of $[\kappa]$. For an ordered tuple $I$, we use $\in_{()}$ to denote membership in $I$.

Observe that $Q$ does not depend on any of $z_{\{1\}},\ldots z_{\{\kappa\}}$. By construction, $Q$ contains no constant term, so $\widehat{Q}(\emptyset)=0$. Clearly $Q(z)\geq-5$ for all $z$ because (11) is always at least $-5$.

Now we lower bound the value of $Q$ on all $z$ that satisfy $H_{\kappa}$. We first show that for any $z^{\prime}$ that strongly satisfies the Huang predicate, $Q(z^{\prime})=5$, then bound $Q(z^{\prime})-Q(z)$ for any $z$ with Hamming distance at most $\kappa$ from $z^{\prime}$. By definition, for each $z^{\prime}_{T_{i}}$, we have that $z^{\prime}_{T_{i}}\prod_{j\in T_{i}}z^{\prime}_{j}=1$. So for each monomial of $Q$,

where the last line follows from the fact that $\sum_{1=1}^{4}1_{\{T_{i}\ni j\}}=2.$ Because there are $5\cdot|\mathcal{Z}_{6}|$ monomials in $Q$, their sum is $5$.

Now we consider the case where $z$ does not strongly satisfy the Huang Predicate, but $H_{\kappa}(z)=1$. Any singleton index on which $z$ and $z^{\prime}$ differ will not change the value of $Q$. Let $N=\{T:z_{T}\neq z^{\prime}_{T}\}$. We lower bound $Q$ by counting the number of monomials in which each $z_{T}$ appears and

For fixed $T$, the number of monomials containing the variables of $z_{T}$ is

because there are exactly $120$ ways to permute the three indices of $T$ in I and the remaining $\kappa-3$ indices are permuted in the remaining 3 positions of $I$. So

If we instead choose to scale $Q$ by a factor of $\tfrac{1}{5}\cdot\frac{\kappa^{2}-3\kappa+2}{2\kappa^{2}-6\kappa-44}$ rather than substituting $\kappa=9$ into (12), we can achieve a better separation of $\delta=\tfrac{\kappa^{2}-3\kappa-46}{2\kappa^{2}-6\kappa-44}$. For $\kappa\geq 9$, this expression is strictly increasing and it approaches $\tfrac{1}{2}$ as $\kappa$ grows.

3 Hamming weight predicates

The remaining predicates we would like to examine are symmetric, meaning they are functions only of their Hamming weights. Again for each predicate $P$ we present a multivariate polynomial that $\delta$-separates $P$ for some $0\leq\delta\leq 1$. Each of these polynomials can also be written as a univariate polynomial on the Hamming weight of its input, which we will use to show that each of the following polynomials $\delta$-separates its predicate for the appropriate value of $\delta$. We give the construction below.

For $z\in\{-1,1\}^{k}$ where $z=z_{1},\ldots,z_{k}$, define $S_{z}=\sum_{i=1}^{k}z_{i}$ and call $S_{z}$ the Hamming weight of $z$.

Note that this is analogous to the notion of a Hamming weight of a vector in $\{0,1\}^{k}$, but differs in that it is not simply the count of the number of $1$’s. We define a general predicate that is satisfied when $S_{z}$ is at least some fixed threshold value $\theta$.

Because the multilinear separating polynomials we will use are symmetric, we present a transformation to an equivalent univariate polynomial on the Hamming weight of the original input.

Then $Q(z)=Q_{u}(S_{z})$ for all $z\in\{-1,1\}^{k}$.

where $\mathscr{K}_{i}(\nu;k)=\sum_{j=0}^{i}(-1)^{j}{\nu\choose i}{k-\nu\choose i-j}$ denotes the Krawtchouk polynomial of degree $i$ [Kra29, KL96]. Substituting $\nu=\frac{k-S_{z}}{2}$, yields the following expressions. In [KL96] the first three expressions are given explicitly and the fourth can be easily obtained by applying their recursive formula.

Finally, substituting these expressions into (14) and by some algebra,

As a consequence, by choosing values of $a,b,c,$ and $d$, we can work with a univariate polynomial while ensuring that its multivariate analogue is unbiased and has degree at most 4 (degree 3 when $d=0$).

Daniely et al. define the following predicate in order to show hardness of improperly learning intersections of four halfspaces.

Then by Lemma 5.8, for all $z\in\{-1,1\}^{k}$, $Q(z)=Q_{u}(S_{z})$. It therefore suffices to lower bound $Q_{u}(s)$ both when $s\geq-1$ and for all $s\in[-k,k]$.

First we show that $Q_{u}$ is monotonically increasing in $s$.

which is evidently positive for $k\geq 5$.

Because $Q$ is monotonically increasing in $s$, $Q_{u}(s)\geq Q_{u}(-k)$ for all $s\in[-k,k]$.

which is clearly negative for $k\geq 5$. Now it just remains to lower-bound $Q_{u}(s)$ for $s\geq-1$. Again, since $Q_{u}$ is monotonically increasing in $s$, we use the value $Q_{u}(-1)$:

Because $\textrm{VAR}_{0}(I_{8k})$ is evidently $\Omega(k)$ and $\overline{I_{8k}}<\tfrac{1}{7}$ for all $k\geq 5$, we have the following Corollary.

For odd $k\geq 5$ and sufficiently large $n$, there exists an efficient algorithm that distinguishes between random instances of $\textrm{CSP}(I_{8k})$ with \mathchoice{\hbox{\displaystyle\widetilde{O}}}{\hbox{\textstyle\widetilde{O}}}{\hbox{\scriptstyle\widetilde{O}}}{\hbox{\scriptscriptstyle\widetilde{O}}}(n^{3/2}) constraints and satisfiable instances with high probability.

4 Majority and hardness of approximately agnostically learning halfspaces

Then by Lemma 5.8, for all $z\in\{-1,1\}^{k}$, $Q(z)=Q_{u}(S_{z})$. To simplify $Q$, let $\sigma=sk^{-1/2}$. Then we can rewrite (18) as follows:

where the last inequality follows from the fact that $k\geq 24$ and the first two terms are always nonnegative.

Next we lower-bound $Q_{u}(s)$ for $s>0$.

5 Predicates satisfied by strings with Hamming weight at least −Θ⁡(k)-\Theta(\sqrt{k}).

In light of the fact that the threshold based predicates above are not $4$-wise supporting, one may attempt to find another threshold-based predicate. Here we show that a symmetric threshold predicate that is $4$-wise supporting must be satisfied by all strings with Hamming weight at least $-\tfrac{\sqrt{k}}{2}$. Furthermore, there exists a symmetric threshold predicate that is $4$-wise supporting with a threshold of $-\Theta(\sqrt{k})$ and we sketch its construction.

Again, for simplicity we set $\sigma=sk^{-1/2}$ and obtain the following expression:

Observe that for $k\geq 99$, $\tfrac{1}{k}\left(\tfrac{8}{3}\sigma^{2}+\tfrac{2}{3}\sigma-2\right)=\tfrac{2}{3k}\left(\left(2\sigma-\tfrac{1}{4}\right)^{2}-\tfrac{49}{16}\right)>-\tfrac{1}{48}$. We now lower-bound the value of $Q_{u}$ for $s\geq-\tfrac{1}{2}k^{1/2}$, or equivalently, $\sigma\geq-\tfrac{1}{2}$:

The first three terms are always nonnegative, so $Q_{u}(s)\geq-\tfrac{14}{3}$.

Applying Lemma 5.1, $T_{k}^{-\tfrac{1}{2}\sqrt{k}}$ is $\tfrac{1}{255}$-far from supporting a $4$-wise uniform distribution. ∎

Assume $k=2^{m}-1$ for some integer $m\geq 3$. Then there exists a $4$-wise uniform distribution supported only on $z\in\{-1,1\}^{k}$ such that $S_{z}\geq 1-2\sqrt{k+1}$.

Let $\mathcal{C}$ be a binary BCH code of length $k$ with designed distance $2\iota+1$ and let $\mathcal{C}^{\bot}$ be its dual. Then the uniform distribution on the codewords of $\mathcal{C}$ is $2\iota$-wise uniform [ABI86, MS77]; see also [AS04, Ch 16.2].

Let $c=c_{1}\ldots c_{k}$ be a codeword of $\mathcal{C}^{\bot},$ where each $c_{i}\in\{-1,1\}$. The Carlitz-Uchiyama bound [MS77, page 280] states that for all $c\in\mathcal{C}^{\bot}$,

Observe that the quantity $\tfrac{1}{2}(1-c_{i})$ simply maps $c_{i}$ from $\{-1,1\}$ to $\{0,1\}$ so that we can write the bound to match the presentation in [MS77]. Therefore,

Setting $\iota=2$, we can obtain $4$-wise uniformity on this distribution and each string in the support of the distribution has Hamming weight at least $-1-2\sqrt{k+1}.$ ∎

In order to construct a $4$-wise uniform distribution for any value of $k$, one could simply express $k$ as a sum of powers of 2, construct separate distributions on disjoint variables as described above for each power of 2 (down to the minimum length for which we can achieve distance at least $5$, after which point we use the uniform distribution, and obtain a $4$-wise uniform distribution. The total Hamming weight of a vector supported by this distribution would then be at least $-O(\sqrt{k})$.

SOS refutation proofs

with $\deg(u_{0})\leq d$, $\deg(u_{i}q_{i})\leq d$ for all $i\in[m]$, and $\deg(v_{i}r_{i})\leq d$ for all $i\in[m^{\prime}]$. If it also holds that $u_{0},u_{1},\ldots,u_{m}=0$, we will write $A\vdash_{d}s=0$.

It is well-known that a degree-$d$ SOS proof can be found using an SDP of size $n^{O(d)}$ if it exists [Sho87, Par00, Las00, Las01].

In this section, we will take the set $A$ to be $\{x_{i}^{2}=1\}_{i\in[n]}$, enforcing that variables are $\pm 1$-valued. We show that with high probability there exists a low-degree SOS proof that a polynomial representing the value of a CSP instance is close to its expectation.

For more information on the SOS proof system and its applications to approximation algorithms, see, e.g., [OZ13, Lau09].

2 SOS certification of quasirandomness

All of our SOS results rely on the following theorem, which is the SOS version of Theorem 4.1.

For $k\geq 2$ and $p\geq n^{-k/2}$, let $\{w(T)\}_{T\in[n]^{k}}$ be independent random variables such that for each $T\in[n]^{k}$,

This theorem was essentially proven by Barak and Moitra [BM15]. We give a proof in Appendix A.3. We first use this theorem to show that an SOS version of Lemma 4.4 holds.

We sketch the differences from the proof of Lemma 4.4 given in Section 4.4. For $s\geq 2$, the lemma follows by using Theorem 6.2 instead of Theorem 4.1. If $s=1$, it suffices to show that

for any $v$ since summing over all $i$ as in (10) finishes the proof. If $v_{i}\geq 0$, observe that

If $v(i)<0$, we use $(x_{i}+1)^{2}$ instead of $(x_{i}-1)^{2}$. ∎

The lemma implies an SOS version of Lemma 4.3. To make this precise, we define a specific polynomial representation of $\widehat{D_{\mathcal{I},x}}(S)$:

where $x_{T}^{S}=\prod_{i\in S}x_{T_{i}}$. Note that this is a polynomial in the $x_{i}$’s.

We can show these polynomials are not too large.

Let $\emptyset\neq S\subseteq[k]$ with $|S|=s$. Then

with high probability, assuming also that $\overline{m}\geq\max\{n^{s/2},n\}$.

Based on Lemma 3.13, we will think of Lemma 6.4 as giving an SOS proof of quasirandomness. Below, we use it to prove SOS versions of Theorems 4.6 and 4.9.

3 Strong refutation of any kk-CSP

We can then give an SOS proof strongly refuting CSP($P$).

with high probability when $\overline{m}\geq\frac{2^{O(k)}n^{k/2}\log^{5}n}{\gamma^{2}}$.