Strongly Refuting Random CSPs Below the Spectral Threshold

Introduction

Random instances of constraint satisfaction problems (CSPs) have been a subject of intense study in computer science, mathematics and statistical physics. Even if we restrict our attention to random $k$-SAT, there is already a vast body of work across various communities–see [Ach09] for a survey. In this paper, our focus is on refuting random CSPs: the task of algorithmically proving that a random instance of a CSP is unsatisfiable. Refutation is a well-studied problem with connections to myriad areas of theoretical computer science including proof complexity [BB02], inapproximability [Fei02], SAT solvers, cryptography [ABW10], learning theory [DLS14], statistical physics [CLP02] and complexity theory [BKS13].

For the sake of concreteness, we will for a moment restrict our attention to $k$-SAT, the most well-studied random CSP. In the random $k$-SAT model, we choose a $k$-uniform CNF formula $\Phi$ over $n$ variables by drawing $m$ clauses independently and uniformly at random. The density of $\Phi$ is given by the ratio $\alpha=m/n$. It is conjectured that for each $k$, there is a critical value $\alpha_{k}$ such that $\Phi$ is satisfiable with high probability if $\alpha<\alpha_{k}$, and unsatisfiable with high probability for $\alpha>\alpha_{k}$. Such phase transition phenomena are conjectured to occur for all nontrivial random CSPs; for the specific case case of $k$-SAT, it was only recently rigorously established for all sufficiently large $k$ [DSS15].

In the unsatisfiable regime, when $\alpha>\alpha_{k}$, the natural algorithmic problem we associate with random $k$-SAT formulas is the problem of refutation. We define the notion of a refutation algorithm formally:

(Refutation Algorithm) An algorithm $\mathcal{A}$ is a refutation algorithm for random $k$-SAT at density $\alpha$, if given a random instance $\Phi$ of $k$-SAT with density $\alpha$, the algorithm $\mathcal{A}$:

Outputs YES with probability at least $\frac{1}{2}$ over the choice of $\Phi$.The choice of the fraction $\frac{1}{2}$ here is arbitrary, and one could potentially consider any fixed constant.

Note that if the algorithm $\mathcal{A}$ outputs YES on an instance $\Phi$, it certifies that the instance $\Phi$ is unsatisfiable.

At densities far exceeding the unsatisfiability threshold, i.e., $\alpha\gg\alpha_{k}$, a simple union bound argument can be used to show that a random instance $\Phi$ has no assignment satisfying more than a $1-\frac{1}{2^{k}}+\delta(\alpha)$ fraction of constraints, where $\delta(\alpha)\to 0$ as $\alpha\to\infty$. In this regime, a natural algorithmic task is strong refutation:

(Strong Refutation) An algorithm $\mathcal{A}$ is a strong refutation algorithm for random $k$-SAT at density $\alpha$, if for a fixed constant $\delta>0$, given a random instance $\Phi$ of $k$-SAT with density $\alpha$, the algorithm $\mathcal{A}$:

Outputs YES with probability at least $\frac{1}{2}$ over the choice of $\Phi$.

Outputs NO if $\Phi$ has an assignment satisfying at least a $(1-\delta)$-fraction of clauses.

An important conjecture in complexity theory is Feige’s “R3SAT hypothesis,” which states that for any $\delta>0$, there exists some constant $c$ such that there is no polynomial-time algorithm that can certify that a random $3$-SAT instance has value at most $1-\delta$ (that is, strongly refute $3$-SAT) at clause density $m/n=c$. Feige exhibited hardness of approximation results based on the hypothesis for a class of otherwise elusive problems such as densest-$k$ subgraph and min-bisection [Fei02]. This hypothesis has subsequently been used as the starting point in a variety of reductions (see e.g. [AAM+11, BKS13, DLS13]).

The problem of strong refutation is non-trivial even for polynomial-time solvable CSPs such as $k$-XOR. The weak refutation problem for $k$-XOR can be easily solved using Gaussian elimination. A random $k$-XOR instance $\Phi$ on $n$ variables $x_{1},\ldots,x_{n}\in\{\pm 1\}$ consists of $m$ equations of the form $x_{i_{1}}\cdot x_{i_{2}}\cdots x_{i_{k}}=\pm 1$ By a simple union bound, one can show that at all super-linear densities $m/n=\omega(1)$, with high probability, no assignment satisfies more than $\frac{1}{2}+o(1)$-fraction of the equations.Random $k$-XOR can also be equivalently defined in terms of equations of the form $x_{i_{1}}\oplus\cdots x_{i_{k}}=0/1$. The equivalence follows by mapping $0\to 1$, $1\to-1$, and $\oplus\to\cdot$. The problem of strong refutation for random $k$-XOR amounts to certifying that no assignment satisfies more than $1-\delta$ fraction of equations for some constant $\delta>0$. A natural spectral algorithm can efficiently strongly refute $k$-XOR at densities $m/n\geq n^{k/2-1}$ [CGL04, CGL07, AOW15, BM15]. However, strong refutation at any lower density is widely believed to be an intractable problem [ABW10, BM15, DLS14, Dan15]. We refer the reader to [Dan15] for a survey of the evidence pointing to the intractability of the problem.

To expose the stark difficulty of strongly refuting random $k$-XOR, consider the easier task of distinguishing random $k$-XOR instances from those generated from the following distribution: first, sample a satisfiable instance of $k$-XOR uniformly at random, by sampling a planted solution $z\in\{\pm 1\}^{n}$ and randomly choosing $m$ equations, each on $k$ variables, satisfied by $z$. Then, corrupt each of the $m$ equations (so that $z$ does not satisfy it) with probability $\delta$. Equivalently, this problem can be described as learning parity with noise, wherein $z\in\{\pm 1\}^{n}$ defines the unknown parity and each equation $C_{i}$ is an example to the learning algorithm. An algorithm to learn parity from noisy examples can be used to distinguish the planted instances sampled as described above from uniformly random instances of $k$-XOR. There is no known distinguishing algorithm at any density $m/n<n^{k/2-1}$, and the computational intractability of this problem has recently been used to obtain lower bounds for improper learning [Dan15].

A natural proof system for strong refutation is the sum-of-squares (SoS) proof system. Given an instance $\Phi$ of a Boolean $k$-CSP, the fraction of constraints satisfied by an assignment $x$ can be written as a polynomial $P_{\Phi}(x)$ of degree at most $k$ in $x$. Let $\operatorname{opt}(\Phi)$ denote the largest fraction of constraints satisfied by any assignment to the variables, i.e.,

Therefore, certifying an upper bound $c$ on $\operatorname{opt}(\Phi)$ reduces to certifying that $\max_{x\in\{\pm 1\}^{n}}P_{\Phi}(x)<c$.

A degree-$d$ sum-of-squares proof for this fact is a polynomial identity of the form,

where $\deg(q_{i}^{2})\leq d$ and $\mathcal{I}$ is the ideal generated by the polynomials $\{x_{j}^{2}-1\}$ that define the variety $\{\pm 1\}^{n}$.

The size of a degree-$d$ SoS proof is at most $n^{O(d)}$, assuming the coefficients have a bit-complexity of at most $n^{O(d)}$. Moreover, finding a degree-$d$ SoS proof can be formulated as a semidefinite program, also known as the degree-$d$ sum-of-squares hierarchy or the $d$-round Lasserre/Parrillo SDP hierarchy [Las00, Par00]. Therefore, if there is a degree-$d$ SoS proof with bit complexity $n^{O(d)}$, then one can be found in time $n^{O(d)}$.

SoS proof systems are very powerful in that they capture both local arguments, such as resolution-based proofs, and global methods like spectral techniques. Furthermore, these proof systems subsume various linear programming and SDP hierarchies such as the Sherali-Adams, Lovász Schrijver (LS) and LS+ hierarchies. In the recent past, the SoS SDP hierarchy has received considerable attention due to its ability to certify the objective value on many candidate hard instances for the unique games problem [BBH+12].

Unfortunately, the lower bounds of Grigoriev [Gri01] and Schoenebeck [Sch08] rule out efficient strong SoS refutations for random $k$-XOR and random $k$-SAT at densities significantly smaller than $m/n<n^{k/2-1}$. Specifically, Schonebeck’s result implies that with high probability over $k$-XOR instances $\Phi$ with clause density $m/n<O(n^{(k/2-1)(1-\delta)})$, the SoS hierarchy cannot refute $\Phi$ at degree $O(n^{\delta})$.

Note that this leaves open the possibility that random $k$-XOR and random $k$-SAT admit subexponential-sized strong refutations well-below the $n^{k/2-1}$ threshold. This sets the stage for our main result.

For all $\delta\in[0,1)$ given a random $k$-XOR instance $\Phi$ on $n$ variables, with high probability over $\Phi$, the degree $O(n^{\delta})$ sum-of-squares hierarchy can strongly refute $\Phi$, certifying that

for any constant $\varepsilon>0$ as long as $\Phi$ has clause density $m/n\geq\widetilde{O}(n^{(k/2-1)(1-\delta)})$, where the $\widetilde{O}$ notation hides logarithmic factors and a dependence on $\varepsilon$ and $k$. Further, there is a spectral algorithm achieving the same guarantees by computing the eigenvalue of an $2^{\widetilde{O}(n^{\delta})}\times 2^{\widetilde{O}(n^{\delta})}$ matrix.

The algorithm from Theorem 1.3 yields tight refutations–certifying a tight upper bound of $\operatorname{opt}(\Phi)+\varepsilon$ for any constant $\varepsilon>0$.

Notice that the result establishes a smooth trade-off between the clause density of $\Phi$ and the running time of the refutation algorithm. Specifically for all $\delta\in[0,1)$, the algorithm strongly refutes at density $m/n=\widetilde{O}(n^{(k/2-1)(1-\delta)})$ in time $\exp(\widetilde{O}(n^{\delta}))$, so that when $\delta=0$ the result matches the performance of the best known polynomial-time algorithms, and at $\delta=1$, the algorithm refutes instances just above the threshold of satisfiability in exponential time. Moreover, the degree of the sum-of-squares refutations matches the degree lower bounds of [Gri01, Sch08] up to polylogarithmic factors.

Feige [Fei02] introduced a connection between the refutation of random XOR instances and the refutation of other CSPs, and this connection was later used in several other works (e.g. [FKO06, AOW15, BM15]). Using the machinery developed by Allen et al. [AOW15], we apply our algorithm for $k$-XOR to refute other random CSPs involving arbitrary Boolean predicates $P$; for example to $k$-SAT.

for any constant $\varepsilon>0$ so long as $\Phi$ has density at least $m/n\geq\widetilde{O}(n^{(k/2-1)(1-\delta)})$, where the $\widetilde{O}$ hides a dependence on a polylog factor, $k$ and $\varepsilon$. Further, there is a spectral algorithm achieving the same guarantees.

We can extend Theorem 1.5 so that the density/runtime trade-off depends on the independence parameter of the predicate $P$ as defined by [AOW15]–we defer the details to Section 5.

Injective tensor norm

The proof techniques we develop are applicable beyond strongly refuting random $k$-XOR, to the problem of certifying upper bounds on the injective tensor norm of random tensors.

The injective tensor norm generalizes the matrix operator norm, in the following sense. For an order-$k$ symmetric tensor with all dimensions equal to $n$, the injective tensor norm is defined as

where by $x^{\otimes k}$ we mean the symmetric rank-1 tensor of order $k$ given by tensoring $x$ with itself, and by the inner product we mean the entry-wise sum of the products of the entries of ${\bf T}$ and $x^{\otimes k}$, as is standard.

When $k=2$, computing $\|{\bf T}\|_{inj}$ is equivalent to computing the matrix operator norm. Yet when $k\geq 3$, the injective tensor norm is hard to compute. The hardness of approximating the injective tensor norm is not fully understood, but we do know that, assuming the exponential-time hypothesis, the injective tensor norm requires quasipolynomial time to approximate, even within super-constant factors [BBH+12]. There are also reductions to the problem from a variety of problems such as Planted Clique [BV09] and Small-Set Expansion [BBH+12].

The problem is nontrivial even when the tensor has i.i.d. random entries. It is well-known that the norm of a tensor with i.i.d. symmetric subgaussian entries is of the same order as the norm of a random matrix:

So the question arises naturally: is it easy to certify tensor norm bounds under distributional assumptions on the entries? The current known polynomial-time algorithms fall short of the bound $\widetilde{O}(\sqrt{n})$, and can only certify bounds of $\|{\bf T}\|_{inj}\leq\widetilde{O}(n^{k/4})$ for tensors of order $k$ [RM14, HSS15, HSSS15]. The algorithm of Hopkins et al. [HSS15] is based on the degree-$k$ SoS relaxation for the tensor norm problem. They also give a lower bound for the SoS relaxation for the order-$3$ tensor at degree $4$, proving that the relaxation has value $\widetilde{\Omega}(n^{3/4})$, which implies that their analysis is tight for the SoS hierarchy at degree $4$.

By applying our techniques for random $k$-XOR refutations to the problem of certifying bounds on tensor norms, we have the following result:

For any $\delta\in[0,1/120)$, given a symmetric order-$k$ tensor ${\bf T}$ with i.i.d. standard Gaussian entries, with high probability over the choice of ${\bf T}$, the degree $O(n^{\delta})$ SoS hierarchy relaxation certifies that

where the $\widetilde{O}$ notation hides a polylogarithmic factor and a dependence on $k$. Furthermore, there is a spectral algorithm that computes the eigenvalues of a $2^{\widetilde{O}(n^{\delta})}\times 2^{\widetilde{O}(n^{\delta})}$ matrix that certifies the same bound.

In an independent work, Bhattiprolu et al. [BGL16] have obtained a result similar to Theorem 1.7 for low-order tensors (for order $k=3,4$); at $k=3,4$, they certify tighter bounds. They also obtain a tight lower bound on the integrality gap of degree-$k$ SoS relaxations for $k$-tensor norms.

Roughly speaking, our spectral algorithm relies mainly on the symmetry constraints in the SDP. In Section 2, we describe how to harness these symmetry constraints to obtain better approximations with increasing SoS degree (by showing how the symmetry constraints can be used to improve a spectral algorithm). This technique adds to the arsenal of tools for algorithm design via the SoS SDP hierarchy, and is the main technical contribution of this work.

1 Related work

We briefly survey the prior work on refuting random CSPs–we refer the reader to [AOW15] for a thorough survey on the topic. Work on refuting random CSPs began with Chvátal and Szemerédi [CS88], who showed that a random $k$-SAT instance with clause density $\alpha>c$ (for $c$ constant) with high probability requires Resolution refutations of exponential size. This lower bound was later complemented by the works of [Fu98, BKPS98], which show that at clause density $\alpha\geq O(n^{k-1})$, polynomial-sized resolution proofs exist and can be found efficiently. At the turn of the century, Goerdt and Krivelevich [GK01] pioneered the spectral approach to refuting CSPs, showing that a natural spectral algorithm gives refutations for $k$-SAT in polynomial time when $\alpha=m/n\geq n^{\lceil k/2\rceil-1}$. A series of improvements followed, first achieving bounds for $\alpha\geq O(n^{1/2+\varepsilon})$ for any constant $\varepsilon$ for the special case of $3$-SAT [FG01, FGK05], then achieving strong refutation at densities $\alpha\geq\widetilde{O}(n^{\lceil k/2\rceil-1})$ [CGL04, CCF10]. Finally, the works of Allen et al. and Barak and Moitra gave spectral algorithms for strongly refuting $k$-XOR and $k$-SAT for any $\alpha\geq\widetilde{O}(n^{k/2-1})$ [AOW15, BM15], and Allen et al. also give a reduction from any CSP which is far from supporting a $t$-wise independent distribution to $t$-XOR. These spectral algorithms are the algorithmic frontier for efficient refutations of random CSPs.

Though not algorithmic, the work of [FKO06] is worth mentioning as well. Feige et al. show that, at clause density $\alpha=m/n\geq\widetilde{O}(n^{0.4})$, there exists a polynomial-sized (weak) refutation for random $3$-SAT given by a subset of $O(n^{0.2})$ unsatisfiable clauses. Understanding whether polynomial-sized weak refutations exist for smaller $\alpha$ is an intriguing open problem.

In a concurrent and independent work, Bhattiprolu et al. [BGL16] obtained a result similar to Theorem 1.7 for bounding the norms of tensors of order $3$ and $4$. The bounds obtained in [BGL16] are tighter for $k=3$ and $k=4$. The results of [BGL16] do not imply new results for refutation even for CSPs of arity $3$ and $4$, since their upper bound is too weak on sparse tensors–a regime that poses additional technical hurdles.

2 Organization

In Section 2, we illustrate our core ideas via a detailed exposition of our proof for certifying bounds on the norm of order-$4$ tensors, and explain how these techniques can be built upon to strongly refute CSPs. Section 3 contains the full proof our tensor norm results. Section 4 contains our results for refuting $k$-XOR instances. In Section 5, we combine our $k$-XOR refutation algorithms with the framework of [AOW15] to refute other CSPs. Finally, in Section 6 we argue that our spectral algorithms give SoS proofs.

3 Preliminaries

Main Ideas: Proof for Random 444-Tensors

In this section, we will survey the main ideas in our paper by proving Theorem 1.7 (our tensor norm certification algorithm) for the case of random $4$-tensors. This specific case yields the simplest proof, while encapsulating the core ideas of our techniques for both injective tensor norm and $k$-XOR. We formally state the injective tensor norm problem here.

First, we briefly outline the connection between $k$-XOR refutation and certifying bounds on tensor norms. Let $\Phi$ be a random $k$-XOR formula on $x\in\{\pm 1\}^{n}$ with $m\approx pn^{k}$ clauses, sampled as follows: for each $S\subset[n]^{k}$ independently with probability $p$, add the constraint that $\prod_{i\in S}x_{i}=\eta_{S}$ where $\eta_{S}$ is a uniform bit $\pm 1$, and with probability $1-p$, add no constraint. We can form an order-$k$ tensor ${\bf T}$ so that for each $S\in[n]^{k}$, ${\bf T}_{S}=0$ if there is no constraint, and otherwise ${\bf T}_{S}=\eta_{S}$.

For any assignment $x\in\{\pm 1\}^{n}$, the inner product $\langle{\bf T},x^{\otimes k}\rangle$ is equal to the difference in the number of $\Phi$’s constraints that $x$ does and does not satisfy. Since $\Phi$ has $m$ constraints in all, certifying that $\max_{x\in\{\pm 1\}^{n}}|\langle{\bf T},x^{\otimes k}\rangle|\leq o(m)$ is equivalent to certifying that $\operatorname{opt}(\Phi)\leq\tfrac{1}{2}+o(1)$. On the other hand, certifying the injective tensor norm amounts to exhibiting an upper bound on $\max_{\lVert y\rVert\leq 1}|\langle{\bf T},y^{\otimes k}\rangle|$ where the maximization is over all unit vectors $y$. Every Boolean vector $x\in\{\pm 1\}^{n}$ is of length $\lVert x\rVert=\sqrt{n}$, which implies that $\max_{x\in\{\pm 1\}^{n}}|\langle{\bf T},x^{\otimes k}\rangle|\leq n^{k/2}\cdot\lVert{\bf T}\rVert_{inj}$.

In what follows, we will give a spectral algorithm for Problem 2.1 for random $4$-tensors with i.i.d. subgaussian entries. We will show that this spectral algorithm is subsumed by a SoS relaxation of appropriate degree in Section 6. The rest of this section is organized as follows.

We first describe the matrix whose maximum eigenvalue provides the upper bound on the injective tensor norm. Rather than writing down the matrix immediately, we will build up our intuition by first considering a simple spectral approach, and then seeing how we can improve.

We then obtain bounds on the eigenvalues of the matrix, which will hold with high probability for tensors with i.i.d. subgaussian entries–this is the step in which we analyze the performance of our algorithm. Because our matrix is somewhat complicated and not amenable to the application of black-box matrix concentration inequalities, we will apply the trace power method. This amounts to bounding the expected trace of a large power of our matrix, a goal which we split in to two steps.

First, we reduce computing the expected trace to a hypergraph counting problem.

Then, we simplify the counting by analyzing a particular hypergraph sampling process.

1 Improving on the natural spectral algorithm with higher-order symmetries

A natural spectral algorithm for Problem 2.1 is to flatten the tensor to a matrix, and then compute the operator norm of the matrix. This is a valid relaxation because, given an order-$4$ tensor ${\bf A}$ with symmetric i.i.d. standard normal entries, if we take $A$ to be the natural $n^{2}\times n^{2}$ matrix flattening of ${\bf A}$,

So $\|A\|_{op}$ gives a valid upper bound for $\|{\bf A}\|_{inj}$. This is great–on the left, we have a program that we cannot efficiently optimize, and on the right we have a relaxation which we can compute in polynomial time.

A tensored vector of the form $x\otimes x$ satisfies the symmetry that $(x\otimes x)_{ij}=(x\otimes x)_{ji}=x_{i}x_{j}$. Therefore, a natural approach to decrease the spectrum of $A$ along the non-tensor product directions is to average the matrix $A$, along these symmetries. Specifically, for each $(i,j)$, we would average the $ij^{th}$ and $ji^{th}$ rows, and then repeat the same operation on columns. Formally, the averaged matrix $A^{\prime}$ is given by,

where $\hat{\mathcal{S}}_{2}$ is the set of matrices which perform the permutations corresponding to the symmetric group on $2$ elements on the rows and columns of matrices indexed by $[n]^{2}$. Unfortunately, for a symmetric $4$-tensor ${\bf A}$, the matrix $A$ is also symmetric with respect to these operations, so that $A^{\prime}=A$.

The operator norm of the above described matrix will certify our upper bounds:

The sequence of calculations culminating in (2.2) gives the proof. ∎

Now, how can this give an improved upper bound over $\|A^{\otimes d}\|_{op}=\|A\|_{op}^{d}$? The reason is that although ${\bf A}$ had $4$-wise symmetry, the tensor ${\bf A}^{\otimes d}$ does not have $4d$-wise symmetry. For $I,J\in[n]^{2d}$, $I=(i_{1},i^{\prime}_{1}),\ldots,(i_{d},i^{\prime}_{d})$ and $J=(j_{1},j^{\prime}_{1}),\ldots,(j_{d},j^{\prime}_{d})$ and for permutations $\pi,\sigma$ on $2d$ elements,

By Wigner’s semicircle law, matrices with independent entries have eigenvalues that are all roughly of the same magnitude. Because our matrix has roughly independent entries, we may hope that the semicircle law holds for us, so that from the above heuristic calculations and from (2.2),

Thus, we expect that as we increase $d$, and therefore increase the symmetry of the tensored vectors $x\otimes x$ relative to the “noisy” non-tensor product eigenvectors of $A$, we can certify a tighter upper bound on $\|{\bf A}\|_{inj}$. Of course, since our certificate is the eigenvalue of a $n^{2d}\times n^{2d}$ matrix, the running time the refutation algorithm grows exponentially in the choice of $d$.

2 Matrix concentration for the certificate

Our algorithm is now clear: we form our matrix certificate by averaging overrows and columns corresponding to permutations of row and column indices in $A^{\otimes d}$, then use the certificate matrix’s eigenvalues to upper bound $\|{\bf A}\|^{d}_{inj}$ (by Proposition 2.2).

As a corollary of Theorem 2.3 and Proposition 2.2, we get Theorem 1.7 for the case of order-$4$ tensors.

The proof is essentially an application of Markov’s inequality; we give it in Appendix A.

Our reduction is now complete. Because we will be dealing with subgaussian random variables, the entries of ${\bf A}$ will concentrate well enough for us to reduce to the Rademacher case.

2.2 Bounding the probability of an even hypergraph

From Lemma 2.5 and Proposition 2.4, in order to prove Theorem 2.3 it suffices for us to bound

Next, pair up the edges between $I_{j},I_{j+1}$ and merge each pair to form a hyperedge.

We will use step 1 to bound the dependence on $n$, and step 2 to bound the dependence on $d$. In particular, our arguments from Lemma 2.5 give us the following lemma almost immediately:

To use (2.4), we need to relate the probability that the edges sampled in step 1 have even multiplicity to the probability that the hyperedges sampled in step 2 have even multiplicity.

Balancing the terms concludes the proof; we will fill in the few remaining details in Section 3.1.

3 From k𝑘k-XOR to tensor norms, and odd-order tensors

The proof of Theorem 2.3 generalizes to tensors of all even orders $k$ almost immediately. For odd $k$ we need an extra idea or two, since all natural flattenings of the tensor to a matrix result in a non-square matrix. We give the details for even and odd $k$ in Section 3.1 and Section 3.2 respectively.

Injective Tensor Norm for Subgaussian Random Tensors

In this section, we show how to certify bounds on the norm of a random tensor, building on our proof of the order-$4$ case in Section 2. We handle the even-order and odd-order cases separately, as the odd-order case contains some additional intricacies.

Section 3.1 contains the proof for even tensors. Section 3.2 contains the proof for odd tensors. In Section 3.3, we prove a combinatorial lemma that we rely upon in both proofs.

The case of order-$k$ tensors when $k$ is even is almost completely outlined in Section 2, in the proof overview of Theorem 2.3. Some of the statements from the overview need additional proof, and some need generalization for $k>4$. We briefly fill in the gaps.

Recall that in our setting, we are given a symmetric order-$k$ tensor ${\bf A}$ with i.i.d. standard Gaussian entries, where $k$ is even. Our algorithm consists of computing the operator norm of a certificate matrix; though we described this certificate ion Section 2, we will require one small twist to make our proofs easier:

Input: An order-$k$ dimension-$n$ tensor ${\bf A}$, for even $k$.

Form the asymmetric tensor ${\bf A}^{\prime}$ from ${\bf A}$ as follows. For each $S\in[n]^{k}$,

if $S$ is lexicographically first among all permutations of $S$, set ${\bf A}^{\prime}_{S}=\sum_{\pi\in\mathcal{S}_{k}}{\bf A}_{\pi(S)}$.

Take the natural $n^{k/2}\times n^{k/2}$ matrix flattening $A$ of ${\bf A}^{\prime}$, and form $A^{\otimes d}$.

Letting $\hat{\mathcal{S}}_{dk/2}$ be the set of all permutation matrices that perform the index permutations corresponding to $\mathcal{S}_{dk/2}$ on the rows and columns of $A^{\otimes d}$, form

Output: $\|C_{d}\|^{1/d}$ as a bound on the objective value.

First, we verify the completeness of the certificate:

Let ${\bf A}$ be a symmetric order-$k$ tensor for even $k$, and let $A$ be the natural matrix flattening of ${\bf A}^{\prime}$ the asymmetrization of ${\bf A}$ described in Algorithm 3.1. Let $\mathcal{S}_{dk/2}$ be the symmetric group on $dk/2$ elements, and further let $\hat{\mathcal{S}}_{dk/2}$ be the set of $n^{dk/2}\times n^{dk/2}$ matrices that apply the permutations of $\mathcal{S}_{dk}$ to matrices whose rows and columns are identified with multisets in $[n]^{dk}$. Then

The proof is identical to that of Proposition 2.2, up to noticing that $\langle{\bf A},x^{\otimes k}\rangle=\langle{\bf A}^{\prime},x^{\otimes k}\rangle$. ∎

Now, we will prove that in the case that ${\bf A}$ is a random tensor with i.i.d. subgaussian entries, our certification algorithm improves smoothly upon the simple spectral algorithm as we invest more computational resources.

The proof is nearly identical to the $k=4$ case from Section 2, so we will be brief.

We will assume that each entry of ${\bf A}^{\prime}$ is bounded in absolute value by $\gamma=O(\sqrt{d\log n}))$, as by the subgaussian assumption this is true with high probability, even after symmetrization. This assumption preserves the symmetry of the distribution.

For $H\in\mathcal{H}$ and $V\in\mathcal{V}$, we let $w_{{\bf A}}(V,H)$ denote the product of all hyperedge weights in the hyperedge cycle $(V,H)$ when the weights are given by entries of the tensor ${\bf A}$. Because the entries are distributed symmetrically about , we have that

Sample a random perfect matching (of edges, not hyperedges) between every two consecutive vertex sets $I_{i},I_{i+1}$, letting the configuration of edges we chose be $E$ from the set of all such possible configurations $\mathcal{M}$.

Group the edges between $I_{i}$ and $I_{i+1}$ into groups of size $k/2$, and merge every group into a hyperedge (of order $k$).

Let $(V,E)$ be the intermediate graph in this process that produces the hypergraph $(V,H)$. Notice that now, We restate, then prove, a more precise version of Lemma 2.7

We now prove and apply the following proposition, which is a restatement of Lemma 2.6 for arbitrary $k$:

and the conclusion follows from combining the above with (3.3). ∎

The proof of Lemma 3.7 proceeds by a cute inductive argument, which we will reserve for Section 3.3.

for some constant $c_{\beta}$ depending only on $\beta$. Putting this together with (3.1),(3.2), and (3.4),

for some constant $c^{\prime}_{\beta}$. Choosing $\beta=\frac{2(k-1)\log d}{k(3k-7)\log d+\log n}$ balances the terms, so for smaller $\beta$ we have

Now, requiring that $d\leq n^{1/3k^{2}}$ and choosing $\beta\leftarrow(k-1)\frac{\log d}{\log n}$, we have that

2 Odd-order tensors

In this section, we give our algorithm for certifying bounds on the injective tensor norm of random odd-order tensors. Because there is no canonical way to flatten an odd-order tensor to a square matrix, the algorithm includes an additional step, similar to the one we employ for $k$-XOR instances when $k$ is odd (Section 4.2).

Using the Cauchy-Schwarz inequality, we can bound the injective norm in terms of the matrices $A_{i}$,

Therefore, in order to bound $\|{\bf A}\|_{inj}$, it is sufficient to bound the following quantity.

For a tensor ${\bf A}$ whose entries are i.i.d. subgaussian variables, we bound the value of the maximization problem (3.6).

We can rewrite the polynomial in (3.6) as,

And we can upper bound the latter term by

where we have used the fact that $\|x\|^{2}=1$. Bounding the norm of tensor ${\bf A}$ thus reduces to upper bounding $\langle x^{\otimes 2\kappa},\left(\sum_{i}N_{i}\right)x^{\otimes 2\kappa}\rangle$. Now our strategy is as before–we take a $d$th tensor power of our matrix, then average over the symmetries of $x^{\otimes 2\kappa d}$.

Having discussed the differences between the even and odd cases, we are ready to give our algorithm.

Input: A random tensor ${\bf A}$ of dimension $n$ and odd order $k=2\kappa+1$, and a parameter $d$.

Form the asymmetric tensor ${\bf A}^{\prime}$ as described in Algorithm 3.1, so that $\langle x^{\otimes k},{\bf A}\rangle=\langle x^{\otimes k},{\bf A}^{\prime}\rangle$ but only lexicographically first entries are nonzero.

Let $A_{i}$ be the $n^{\kappa}\times n^{\kappa}$ matrix flattening of the $i$th slice of ${\bf A}^{\prime}$, and form the matrix

Zero out all entries of the matrix corresponding to $(I_{1},I_{2}),(J_{1},J_{2})\in[n]^{2\kappa}$ such that $(I_{1},J_{1})=(I_{2},J_{2})$, forming a new matrix $N$:

Symmetrize the rows and columns of $N^{\otimes d}$ according to the symmetries of $\mathcal{S}_{2d\kappa}$ to obtain the matrix $C$,

Output: The quantity $\left(\|C_{d}\|^{1/d}+\max_{a,b\in[n]^{\kappa}}\sum_{i\in[n]}A_{i}(a,b)^{2}\right)^{1/2}$ as an upper bound on $\|{\bf A}\|_{inj}$.

For any symmetric tensor ${\bf A}$, Algorithm 3.9 outputs a valid upper bound on $\|{\bf A}\|_{inj}$.

Our asymmetrization in step 1 ensures that $\langle x^{\otimes k},{\bf A}\rangle=\langle x^{\otimes k},{\bf A}^{\prime}\rangle$. The proof then follows from the calculations above, beginning at (3.5) and ending at (3.7), and then using that the symmetrization step fixes vectors of the form $x^{\otimes 2d\kappa}$. ∎

We prove that when ${\bf A}$ has subgaussian, centered, independent entries, Algorithm 3.9 improves over the basic spectral algorithm.

For any symmetric tensor ${\bf A}$ with independent subgaussian centered entries, with high probability over the choice of ${\bf A}$, Algorithm 3.9 certifies that

First, the very straightforward observation that subtracting the maximum element cannot have too strong of a negative effect:

If ${\bf A}$ is an order-$D$ tensor with i.i.d. symmetric subgaussian entries, then

The lemma follows from the fact that the variables are subgaussian, and by applying first a Chernoff bound and then a union bound over the indices. ∎

Now, we bound the norm of the matrix $\|C_{d}\|$.

Because the entries of ${\bf A}$ are subgaussian, with high probability all entries of the tensor are bounded in magnitude by $\gamma=O(\sqrt{\kappa\log n})$. We will assume this to be the case in the remainder of the proof.

Interpreting the variables ${\bf A}_{a_{i},c_{i},u_{i}}$ as $k=(2\kappa+1)$-uniform hyperedges, we have that each entry is a sum over hypergraphs indexed by $U\in[n]^{d}$.

For each $U\in[n]^{d}$, we have a hypergraph on the following vertex configuration: on the left, we have the vertices from the multiset $A,B$. On the right, we have the vertices from the multiset $C,D$. In the center, we have the vertices from $U$. On this vertex set, we have $2d$ hyperedges. Of these hyperedges, $d$ form a tripartite matching on the vertices in $A,C,U$, with $\kappa$ vertices from each of $A,C$ and one vertex in $U$. The other $d$ form a similar tripartite matching on the vertices in $B,D,U$. Every hyperedge on $A,C,U$ shares exactly one vertex in $U$ with exactly one hyperedge from $B,D,U$. See Figure 2 for an illustration.

To this end, we describe an equivalent definition of the matrix $C_{(d)}$. Specifically, given $a,b\in[n]^{2\kappa d}$ the entry $C_{(d)}(a,b)$ can be evaluated as follows:

Sample a random matching $\mathcal{E}=\{e_{1},\ldots,e_{2\kappa d}\}$ between the multisets $a$ and $b$.

Group the edges of $\mathcal{E}$ in to $2d$ groups of size $\kappa$, to obtain $2d$ blocks $\mathcal{F}=\{f_{1},\ldots,f_{2d}\}$.

Pick a random matching $\mathcal{M}$ between the blocks in $\mathcal{F}$. Let $\mathcal{M}$ be given by $d$ pairs $\{(h_{i},h_{i}^{\prime})\}_{i\in[d]}$.

For each choice of “pivot vertices” $\sigma\in[n]^{d}$, we get a $(2\kappa+1)$-uniform hypergraph $\mathcal{H}_{\sigma}$ with $2d$ hyperedges given by

The entries of the matrix $C$ are given by,

We will call the hypergraph $\mathcal{H}_{\sigma}$ diagonal-free (or d-free) if there are no pairs of identical blocks matched with each other in $\mathcal{M}$. We will use the notation $\|\cdot\|_{\oplus}$ to denote the number of elements of odd multiplicity in a multiset, and similarly the notation $\|\cdot\|_{0}$ to denote the number of distinct elements in a multiset. We will say $\mathcal{H}_{\sigma}$ is even if the number of occurrences of each hyperedge is even. Now, dividing by our upper bound on the absolute value of the maximum entry,

First we will bound the value of term in (3.9). Recall that by Lemma 3.7, if $\mathcal{E}$ is even then the number of distinct labels in $V\in\mathcal{V}$ is less than $\lVert\mathcal{E}\rVert_{0}$. Therefore,

For every choice of $V\in\mathcal{V},\mathcal{E},\mathcal{F},\mathcal{M}$,

Now we bound (3.8). Using Proposition 3.6 and reasoning similar to that in the proof of Theorem 3.3, by making an analogy between the set of configurations with even $\mathcal{E}$ and the norm of a random matrix under our tensoring and averaging operations, we know that

for a constant $c_{\kappa\beta}$ depending only on $\kappa,\beta$ in Lemma 3.15. By the preceding pair of inequalities, we get that

We can now put together the easy bound on the maximum diagonal entry with the bound on $\|C\|$ to prove Theorem 3.11.

We combine Lemma 3.12 with Theorem 3.13, and we have that with high probability, for constants $c_{\beta}$ and $c_{2}$,

Now, we prove some of the lemmas we have relied upon in the proof of Theorem 3.13. We begin with a lemma bounding the probability that the hyperedges we sample all have even multiplicity.

where $c_{d\beta}$ is a constant depending on $\beta$ and $d$.

Using (3.13) and (3.14) we conclude that,

Since $k<n^{\beta/4}$ and $\beta<1/30$, we have that $k^{1-14\beta}<<n^{\beta/3}$, and so the first term in the latter parenthesis dominates. This implies that,

where $c_{d\beta}$ is a constant depending on $d$ and $\beta$, and where we have used the fact that $8d^{2}\geq 8d^{2}-6d+4$ for all $d\geq 1$.

The following lemma we employ in bounding the probability that our blocks from $\mathcal{F}$ are matched in a way that gives hyperedges with even multiplicity. We do this via reducing the problem to counting the number of multigraphs with labeled edges in which every subgraph induced by a given label is Eulerian.

Define a multigraph $\mathcal{G}$ as follows. In the multigraph $\mathcal{G}$, there is a vertex $v_{f}$ for each distinct block $f\in\mathcal{F}$. There is an edge in $\mathcal{G}$ for each edge in the matchings $\mathcal{M}$ between the blocks. Every choice of pivot vertices $\sigma\in[n]^{k}$ corresponds to a labeling of the edges $\sigma:E(\mathcal{G})\to[n]$. For each edge $e\in E(\mathcal{G})$ incident at a vertex $v_{f}\in V(\mathcal{G})$, there is a hyperedge in $\mathcal{H}_{\sigma}$ corresponding to $(\sigma(e),v_{f})$. The hypergraph $\mathcal{H}_{\sigma}$ is even if and only if for each pivot vertex $i\in[n]$, and each vertex $v_{f}\in V(\mathcal{G})$, the number of edges labeled $i$ incident at $v_{f}$ is even. This implies that $\sigma^{-1}(i)$ form an Eulerian subgraph for each $i\in[n]$. By Lemma 3.17, the number of such labelings $\sigma:E(\mathcal{G})\to[n]$ is at most $(2|E(\mathcal{G})|-2|V(\mathcal{G})|)!\cdot n^{\nicefrac{{E(\mathcal{G})}}{{2}}-\nicefrac{{E_{\oplus}(\mathcal{G})}}{{6}}}$.

Now we are ready to wrap up the proof of the lemma.

Our final lemma of this section is a bound on the number of labelings of a multigraph such that the subgraphs induced by all edge labels are Eulerian, given a bound on the number of multi-edges appearing with odd multiplicity.

Given a multigraph $\mathcal{G}$, a labeling of its edges $\sigma:E(\mathcal{G})\to[n]$ is said to be even, if the preimage of every label $i$ forms an Eulerian subgraph (not necessarily connected) of $\mathcal{G}$. Specifically, the set of edges $\sigma^{-1}(i)\subseteq E(\mathcal{G})$ induce a subgraph where the degree of every vertex is even.

where $|E_{\oplus}(\mathcal{G})|$ is the number of multi-edges with odd multiplicity within $\mathcal{G}$.

We will count the number of even labelings $\sigma$ as follows:

Pick a unordered partition of the edges of the graph in to Eulerian subgraphs. By Claim 3.18, there are at most $(2|E(\mathcal{G})|-2|V(\mathcal{G})|)!$ of them.

Assign a label from $[n]$ to each Eulerian subgraph in the partition. The number of labelings is clearly at most $n^{t}$ where $t$ is the number of subgraphs in the partition. By Claim 3.19, there are at most $\frac{|E(\mathcal{G})|}{2}-\frac{|E_{\oplus}(\mathcal{G})|}{6}$ subgraphs in any partition. Hence, there are at most $n^{\frac{|E(\mathcal{G})|}{2}-\frac{|E_{\oplus}(\mathcal{G})|}{6}}$ labelings for each partition of $\mathcal{G}$ in to Eulerian subgraphs.

The lemma follows immediately from the Claim 3.18 and Claim 3.19 which we will show now.

The number of unordered partitions of the edges of the graph in to Eulerian subgraphs is at most $(2|E(\mathcal{G})|-2|V(\mathcal{G})|)!$.

Let $d_{v}$ denote the degree of vertex $v\in V(\mathcal{G})$. We can specify a partition of the edges of $\mathcal{G}$ in to Eulerian subgraphs, by specifying a sequence of Eulerian traversals whose union covers all the edges in the graph exactly once.

Consider a vertex $v$. Any sequence of traversals induces a matching $M_{v}$ between the edges incident at $v$ – where $e,e^{\prime}$ are matched if one of the traversals goes along $e\rightarrow v\rightarrow e^{\prime}$. Furthermore, given a set of matchings $\{M_{v}|v\in V(\mathcal{G})\}$, it uniquely identifies a set of traversals.

Therefore the number of partitions of $E(\mathcal{G})$ in to Eulerian subgraphs is at most

In any partition of $\mathcal{G}$ in to Eulerian subgraphs, the number of partitions is at most $\frac{|\mathcal{E}(G)|}{2}-\frac{|\mathcal{E}_{\oplus}(G)|}{6}$

Suppose $E(\mathcal{G})=\cup_{i=1}^{t}E_{i}(\mathcal{G})$ denote a partition of $E(\mathcal{G})$ into Eulerian subgraphs. For each edge $e\in E_{i}(\mathcal{G})$ assign a weight $w_{e}=\frac{1}{|E_{i}(\mathcal{G})|}$. By definition of the weights, we have

Note that $w_{e}\leq\frac{1}{2}$ for all $e\in E(\mathcal{G})$, since each subset $E_{i}(\mathcal{G})$ contain at least two edges by virtue of being Eulerian. Moreover, $w_{e}=\frac{1}{2}$ if the edge $e$ belongs to an Eulerian subgraph $E_{i}(\mathcal{G})$ with exactly two edges. In particular, $E_{i}(\mathcal{G})=\{e,e^{\prime}\}$ where $e$ and $e^{\prime}$ form a $2$-cycle. For every multiedge $(a,b)$ with odd multiplicity, at least one of its edges has $w_{e}\leq\frac{1}{3}=\frac{1}{2}-\frac{1}{6}$.

These claims together finish the proof. ∎

3 Useful combinatorial lemmas

Define an $r$-grouping to be a partition of a set of size $c\cdot r$ into $c$ subsets of size $r$. The following lemma bounds the probability that, given a multiset with many distinct elements, an $r$-grouping of the elements results in few $r$-sets with odd multiplicity. We rely on this lemma in our injective tensor norm upper bounds, to bound the probability that a hypergraph sampled from a simple graph has the evenness property.

We will refer to each $s\in[N]$ as a “type”. Call a type $s\in[N]$ infrequent if the number of occurrences of $s$ within $\cup_{i}E_{i}$ is nonzero but at most $8$.

Suppose a type $s\in[N]$ appears exactly once in the sets $E_{1},\ldots,E_{M}$,then irrespective of the choice of the grouping, the group involving $s$ appears exactly once. If there are more than $r\delta Mc$ types that appear exactly once then,

and the lemma holds. Henceforth, we assume that all but $r\delta Mc$ types appear at least twice.

Call a type to be frequent if it occurs more than $8$ times within $\cup_{i}E_{i}$. Out of the $rMc$ elements, at most an $8\beta$ fraction are occurrences of frequent types. Otherwise, the number of distinct types would be less than $rMc\left((1-8\beta)/2+8\beta/8+\delta\right)<\frac{rMc}{2}(1-\beta)$.

Moreover, this implies that the number of distinct frequent types is at most $8\beta rMc/8\leq\beta rMc$. Finally, the number of distinct infrequent types is at least $\frac{rcM}{2}(1-\beta)-\beta rMc\geq\frac{rMc}{2}\cdot(1-3\beta)$.

Let us sample uniform random $r$-groupings $\{G_{i}\}_{i\in[M]}$ one group at a time. Specifically, we will sample groups $g_{1},\ldots,g_{cM}$ where $G_{i}=\{g_{(i-1)c+1},\ldots,g_{ic}\}$, one group at a time. We sample the $i^{th}$ grouping $G_{i}$ as follows:

Pick the element $s$ with the smallest number of ungrouped occurrences left within $\cup_{j=i}^{M}E_{j}$ (breaking ties lexicographically).

Sample the group $g_{(i-1)c+j}$ by picking the remaining $r-1$ elements uniformly at random from ungrouped elements in $E_{i}$

It is clear that the above sampling procedure picks a uniformly random grouping $\{G_{i}\}_{i\in[M]}$.

$s(\mathcal{E}_{i})$ is its final ungrouped occurrence of an infrequent type.

All previous occurrences of $s(\mathcal{E}_{i})$ has been grouped with infrequent types.

There are at least $\beta rc$ ungrouped elements within the current multiset $E_{j}$ that is being grouped.

For every sequence of random choices, the sampling procedure encounters at least $\frac{cM}{2}\cdot(1-(4r+1)\beta)$ critical configurations.

There are at most $8\beta rcM$ occurrences of frequent types. This implies that among the $\frac{rMc}{2}(1-3\beta)$ infrequent labels, at least $\frac{rMc}{2}(1-3\beta)-(8\beta rMc)(r-1)\geq\frac{rMc}{2}(1-(4r-1)\beta)$ are grouped only with infrequent types.

For each of these $\frac{rMc}{2}(1-(4r-1)\beta)$ types there is one final ungrouped occurrence. Even assuming we match all these final occurrences among themselves, both conditions (1) & (2) are met at least $\frac{Mc}{2}(1-(4r-1)\beta)$ times during the sampling procedure.

Finally, there are at most $\beta c$ groups that are picked among the final $\beta rc$ elements within the sets $E_{i}$. Therefore, for at least $\frac{Mc}{2}(1-(4r-1)\beta)-\beta Mc\geq\frac{Mc}{2}(1-(4r+1)\beta)$ steps, $\mathcal{E}_{i}$ is a critical configuration. ∎

Define random variables $\{Z_{i}\}_{i\in[m]}$ as follows:

For all $\alpha\leq\left(\frac{56}{\beta c}\right)^{c-1}$, for all $t\in[cM]$ and all critical configurations $\mathcal{E}_{t}$,

where the maximum is taken over all feasible configurations $\mathcal{E}_{t+1}$ from $\mathcal{E}_{t}$.

At a critical configuration $\mathcal{E}_{t}$, the next group is the last occurrence of $s(\mathcal{E}_{t})$. Recall that $s(\mathcal{E}_{t})$ is infrequent in that it has at most $7$ previous occurrences. Moreover, each of its previous occurrences is grouped to an infrequent type (appearing less than 8 times).

There are at least $\beta rc$ ungrouped elements from which the remaining $r-1$ elements of the group are chosen. For all but at most $(56)^{r-1}$ group choices, the group contains a type $s^{\prime}$ such that this is the first occurrence of $s$ with $s^{\prime}$ in a group.

Therefore, for all but at most $(56)^{r-1}$ choices, the group sampled is its first and only occurrence. In particular, this implies that for a critical configuration $\mathcal{E}_{t}$,

Combining Claim 3.21 and Claim 3.20, we have that

which yields the following concentration bound for all $\delta>0$,

The lemma below shows that in a simple graph formed by matchings with the evenness property, there cannot be too many more distinct vertices than distinct edges.

If each labeled edge appears with multiplicity exactly $2$, then $L\leq m+c$.

In this case, there are exactly $2m$ edges and exactly $2m$ vertices. We proceed by induction on $c$ and $m$. In the base case, we have $c=1$ component with $2$ vertices, in which case we have at most $2$ distinct labels on the vertices, confirming the claim.

Assuming the claim for $c\geq 1$ components and $2m\geq 2$ vertices, consider an instance on $2m+2$ vertices. If all labels appear $\geq 2$ times, we are done, since there are $2m+2$ vertices and thus at most $L\leq m+1$ labels. Otherwise, locate a vertex $v$ whose label has multiplicity $1$.

If $v$ is in a cycle of length $2$, remove $v$ and its neighbor from the graph, obtaining a smaller instance with $L^{\prime}$ labels, $c^{\prime}$ components, and $m^{\prime}$ distinct edge types, with $L^{\prime}+2\geq L$, $c^{\prime}=c-1$, and $m^{\prime}=m$. By the induction hypothesis, $L^{\prime}\leq m^{\prime}+c^{\prime}=m+c-1$, and therefore $L\leq m+1+c$, as desired.

If $v$’s cycle has length $>2$, both $v$’s vertex neighbors must have the same label in order for the edges incident on $v$ to appear twice. We remove $v$ and identify its neighbors, obtaining an instance with $L^{\prime}+1=L$, $m^{\prime}=m$, $c^{\prime}=c$. Appealing to the induction hypothesis, we have $L^{\prime}\leq m^{\prime}+c$, from which we conclude that $L\leq m+1+c$, as desired. ∎

Now, we reduce our lemma to the above case. Say an edge appears with even multiplicity $\mu>2$, and that the labels of the edge are $(a,b)\in[n]^{2}$. We will remove the occurrences of this edge, and put the graph segments back together. When we remove all occurrences of the edge $(a,b)$, we get $3$ kinds of graph segments: paths from $a$–$b$, paths from $a$–$a$, and paths from $b$–$b$. Since $a$, $b$ each have to appear $\mu$ times, we can form a matching between segments of type $a$–$b$, gluing them together at the $a$ endpoint to get a $b$–$b$ segment. Now, we make one cycle by gluing together $a$–$a$ segments, and a separate cycle by gluing together $b$–$b$ segments. Our number of distinct edges has decreased by $1$, and our number of cycles has increased by at most $1$, since we broke up at least one cycle to remove the edge $(a,b)$. We recursively apply this process to our instance, until we reach an instance in which there are only edges of multiplicity $2$, never increasing the quantity $m+c$. In conjunction with our above claim, the conclusion follows. ∎

Refuting Random k𝑘k-XOR Instances

In this section, we give our algorithm for refuting random $k$-XOR instances. In Section 4.1, we describe the algorithm for even $k$; in Section 4.2, we describe the algorithm for odd $k$. We first recall the problem:

A random instance of $k$-XOR with density $\alpha=pn^{(k-1)/2}$ is a formula $\Phi$ on $n$ variables $x\in\{\pm 1\}^{n}$, sampled so that for each $S\in[n]^{k}$:

Independently with probability $p$, add constraint $C_{S}:\prod_{i\in S}x_{i}=\eta_{S}$, for $\eta_{S}$ a uniformly random Rademacher variable.

Otherwise, with probability $1-p$, add no constraint.

We let $m\approx pn^{k}$ be the number of constraints, and for any assignment $x\in\{\pm 1\}^{n}$, $P_{\Phi}(x)$ is the fraction of constraints satisfied by $x$.

Given a random $k$-XOR instance $\Phi$, certify with high probability over the choice of $\Phi$ that for all assignments $x\in\{\pm 1\}^{n}$,

for some constant $\delta\in[0,\nicefrac{{1}}{{2}})$, where $P_{\Phi}(x)$ is the fraction of $\Phi$’s constraints satisfied by $x$.

As described in Section 2, there is a natural random order-$k$ tensor that we can identify with any $k$-XOR instance $\Phi$. Given a $k$-XOR instance $\Phi$ with constraints $C_{1},\ldots,C_{m}$, form the tensor ${\bf T}_{\Phi}$ as follows: for each constraint $C_{i}:\prod_{j\in S_{i}}x_{i}=\eta_{S_{i}}$, set the entry ${\bf T}_{S_{i}}=\eta_{S_{i}}$; in all other entries place a . We then have that for any assignment $x\in\{\pm 1\}^{n}$,

That is, the inner product $\langle{\bf T}_{\Phi},x^{\otimes k}\rangle$ gives the difference between the number of constraints $x$ satisfies and the number of constraints $x$ violates. Our strong refutation algorithm will be based on showing that

for a constant $\delta$ arbitrarily close to .

From (4.1), it is clear that a good bound on $\|{\bf T}_{\Phi}\|_{inj}$ would give a refutation algorithm, and so we could hope that our algorithms for bounding tensor norms would suffice. However, when the probability of sampling a constraint $p\leq n^{-k/2}$, the tensor ${\bf T}_{\Phi}$ becomes sparse enough that its norm is maximized by sparse vectors, so that $\|{\bf T}_{\Phi}\|_{inj}\approx 1$. We are only interested in balanced vector $x\in\{\pm 1\}^{n}$, and so this is a poor upper bound–it will only let us certify that $P_{\Phi}(x)\leq\frac{1}{2}+\frac{n^{k/2}}{m}\geq 1$.