For an @math -variate order- @math tensor @math , define @math to be the maximum value taken by the tensor on the unit sphere. It is known that for a random tensor with i.i.d @math entries, @math w.h.p. We study the problem of efficiently certifying upper bounds on @math via the natural relaxation from the Sum of Squares (SoS) hierarchy. Our results include: - When @math is a random order- @math tensor, we prove that @math levels of SoS certifies an upper bound @math on @math that satisfies [ B A_ ( n q^ ,1-o(1) )^ q 4-1 2 w.h.p. ] Our upper bound improves a result of Montanari and Richard (NIPS 2014) when @math is large. - We show the above bound is the best possible up to lower order terms, namely the optimum of the level- @math SoS relaxation is at least [ A_ ( n q^ ,1+o(1) )^ q 4-1 2 . ] - When @math is a random order- @math tensor, we prove that @math levels of SoS certifies an upper bound @math on @math that satisfies [ B A_ ( O (n) q )^ d 4 - 1 2 w.h.p. ] For growing @math , this improves upon the bound certified by constant levels of SoS. This answers in part, a question posed by Hopkins, Shi, and Steurer (COLT 2015), who established the tight characterization for constant levels of SoS.
@cite_12: Random constraint satisfaction problems (CSPs) are known to exhibit threshold phenomena: given a uniformly random instance of a CSP with @math variables and @math clauses, there is a value of @math beyond which the CSP will be unsatisfiable with high probability. Strong refutation is the problem of certifying that no variable assignment satisfies more than a constant fraction of clauses; this is the natural algorithmic problem in the unsatisfiable regime (when @math ). Intuitively, strong refutation should become easier as the clause density @math grows, because the contradictions introduced by the random clauses become more locally apparent. For CSPs such as @math -SAT and @math -XOR, there is a long-standing gap between the clause density at which efficient strong refutation algorithms are known, @math , and the clause density at which instances become unsatisfiable with high probability, @math . In this paper, we give spectral and sum-of-squares algorithms for strongly refuting random @math -XOR instances with clause density @math in time @math or in @math rounds of the sum-of-squares hierarchy, for any @math and any integer @math . Our algorithms provide a smooth transition between the clause density at which polynomial-time algorithms are known at @math , and brute-force refutation at the satisfiability threshold when @math . We also leverage our @math -XOR results to obtain strong refutation algorithms for SAT (or any other Boolean CSP) at similar clause densities. Our algorithms match the known sum-of-squares lower bounds due to Grigoriev and Schonebeck, up to logarithmic factors. Additionally, we extend our techniques to give new results for certifying upper bounds on the injective tensor norm of random tensors.
@cite_17: Let @math be a nontrivial @math -ary predicate. Consider a random instance of the constraint satisfaction problem @math on @math variables with @math constraints, each being @math applied to @math randomly chosen literals. Provided the constraint density satisfies @math , such an instance is unsatisfiable with high probability. The problem is to efficiently find a proof of unsatisfiability. We show that whenever the predicate @math supports a @math - probability distribution on its satisfying assignments, the sum of squares (SOS) algorithm of degree @math (which runs in time @math ) refute a random instance of @math . In particular, the polynomial-time SOS algorithm requires @math constraints to refute random instances of CSP @math when @math supports a @math -wise uniform distribution on its satisfying assignments. Together with recent work of [LRS15], our result also implies that polynomial-size semidefinite programming relaxation for refutation requires at least @math constraints. Our results (which also extend with no change to CSPs over larger alphabets) subsume all previously known lower bounds for semialgebraic refutation of random CSPs. For every constraint predicate @math , they give a three-way hardness tradeoff between the density of constraints, the SOS degree (hence running time), and the strength of the refutation. By recent algorithmic results of [AOW15] and [RRS16], this full three-way tradeoff is , up to lower-order factors.
Raghavendra, Rao, and Schramm @cite_12 also prove results analogous to d-tensor:informal for the case of random polynomials (a model we do not consider in this work, and which appears to pose additional technical difficulties). This implied upper bounds for refuting random instances of constraint satisfaction problems using higher levels of the SoS hierarchy, which were shown to be tight via matching SoS lower bounds in @cite_17 .