We analyze the sum-of-squares rank of unweighted instances of the Minimum Knapsack (MK) problem, i.e., minimization of \(\sum _{i=1}^n x_i\) for 0/1 variables under the constraint \(\sum _{i=1}^n x_i \ge q\), with \(q \in \mathbb {R}\). Such instances have long served as a testbed for understanding the limitations of lift-and-project methods in Boolean optimization. For example, both the Lovász–Schrijver and Sherali–Adams hierarchies require (maximal) rank n to solve them, already when q = 1/2 is constant. The SOS hierarchy requires only sublinear rank \(O(\sqrt {n})\) to solve unweighted MK when q = 1/2. On the other hand, when q is allowed to vary with n, the SOS rank of the problem may become linear. Interestingly, this is known to happen both when q is large, and when q is very small (0 < q ≤ 2− n). This raises the question of whether we should think of hard instances of unweighted MK as being typical for the SOS hierarchy, or as a consequence of very specific choices of the threshold parameter q.
We analyze the sum-of-squares rank of unweighted instances of the Minimum Knapsack (MK) problem, i.e., minimization of (\sum _{i=1}^n x_i) for 0/1 variables under the constraint (\sum _{i=1}^n x_i \ge q), with (q \in \mathbb {R}). Such instances have long served as a testbed for understanding the limitations of lift-and-project methods in Boolean optimization. For example, both the Lovász–Schrijver and Sherali–Adams hierarchies require (maximal) rank n to solve them, already when q = 1/2 is constant. The SOS hierarchy requires only sublinear rank (O(\sqrt {n})) to solve unweighted MK when q = 1/2. On the other hand, when q is allowed to vary with n, the SOS rank of the problem may become linear. Interestingly, this is known to happen both when q is large, and when q is very small (0 < q ≤ 2− n). This raises the question of whether we should think of hard instances of unweighted MK as being typical for the SOS hierarchy, or as a consequence of very specific choices of the threshold parameter q.
We analyze the sum-of-squares rank of unweighted instances of the Minimum Knapsack (MK) problem, i.e., minimization of ∑i=1nxi for 0/1 variables under the constraint ∑i=1nxi≥q, with q∈R. Such instances have long served as a testbed for understanding the limitations of lift-and-project methods in Boolean optimization. For example, both the Lovász-Schrijver and Sherali-Adams hierarchies require (maximal) rank n to solve them, already when q=1/2 is constant. The SOS hierarchy requires only \emph{sublinear} rank O(n) to solve unweighted MK when q=1/2. On the other hand, when q is allowed to vary with~n, the SOS rank of the problem may become linear. Interestingly, this is known to happen both when q is large, and when q is very small ($0
We analyze the sum-of-squares rank of unweighted instances of the Minimum Knapsack (MK) problem, i.e., minimization of for 0/1 variables under the constraint, with. Such instances have long served as a testbed for understanding the limitations of lift-And-project methods in Boolean optimization. For example, both the Lovász-Schrijver and Sherali-Adams hierarchies require (maximal) rank n to solve them, already when q = 1/2 is constant. The SOS hierarchy requires only sublinear rank to solve unweighted MK when q = 1/2. On the other hand, when q is allowed to vary with n, the SOS rank of the problem may become linear. Interestingly, this is known to happen both when q is large, and when q is very small (0 < q ≤ 2-n). This raises the question of whether we should think of hard instances of unweighted MK as being typical for the SOS hierarchy, or as a consequence of very specific choices of the threshold parameter q. In this paper, we address this question by showing new upper and lower bounds on the SOS rank of unweighted MK in the whole regime of the parameter q. For n-q ≤ O(1), we show that the SOS rank is constant. In contrast, when q ≤ O(1), a linear rank is needed if q is exponentially close to an integer. As our main positive result, we show that linear rank is very rare for q ≤ O(1). This can be expressed in the language of smoothed analysis: After perturbing q by a Gaussian with mean 0 and variance σ2, the expected SOS rank of MK is.
We study the rank of the Sum of Squares (SoS) hierarchy over the Boolean hypercube for Symmetric Quadratic Functions (SQFs) in n variables with roots placed in points k - 1 and k. Functions of this type have played a central role in deepening the understanding of the performance of the SoS method for various unconstrained Boolean hypercube optimization problems, including the Max Cut problem. Recently, Lee, Prakash, de Wolf, and Yuen proved a lower bound on the SoS rank for SQFs of Ω(√k(n - k)) and conjectured the lower bound of Ω(n) by similarity to a polynomial representation of the n-bit OR function. Leveraging recent developments on Chebyshev polynomials, we refute the Lee-Prakash-de Wolf- Yuen conjecture and prove that the SoS rank for SQFs is at most O(√nk log(n)). We connect this result to two constrained Boolean hypercube optimization problems. First, we provide a degree O(√n) SoS certificate that matches the known SoS rank lower bound for an instance of Min Knapsack, a problem that was intensively studied in the literature. Second, we study an instance of the Set Cover problem for which Bienstock and Zuckerberg conjectured an SoS rank lower bound of n/4. We refute the Bienstock-Zuckerberg conjecture and provide a degree O(√n log(n)) SoS certificate for this problem.
Chvátal--Gomory cuts (CG-cuts) and the Bienstock--Zuckerberg hierarchy capture useful linear programs that the standard bounded degree sum-of-squares (SoS) hierarchy fails to capture. In this paper we present a novel polynomial time SoS hierarchy for 0/1 problems with a custom subspace of high degree polynomials (not the standard subspace of low degree polynomials). We show that the new SoS hierarchy recovers the Bienstock--Zuckerberg hierarchy. Our result implies a linear program that reproduces the Bienstock--Zuckerberg hierarchy as a polynomial-sized, efficiently constructible extended formulation that satisfies all constant pitch inequalities. The construction is also very simple, and it is fully defined by giving the supporting polynomials. Moreover, for a class of polytopes (e.g., set cover and packing problems), the resulting SoS hierarchy optimizes in polynomial time over the polytope resulting from any constant rounds of CG-cuts, up to an arbitrarily small error in the solution value. Arguably, this is the first example where different basis functions can be useful in asymmetric situations to obtain a hierarchy of relaxations.
We develop an argmax principle for analyzing sum-of-squares relaxations of optimization problems over the unit sphere. Given a feasible pseudo-expectation, we form a polynomial of high-order pseudo-moments, such as Φk(u)=E⟨x,u⟩2k. Our guiding principle is that its maximizers are rounding candidates: their local and global optimality conditions reveal the reweighed pseudo-expectation inequalities governing SoS convergence. This viewpoint unifies several problems previously analyzed by rather different techniques.
We obtain three results. First, for Best Separable State, we give a degree-O(n/ε) SoS analysis for approximating hsep(P) in the perfect-completeness regime, improving and simplifying Barak, Kothari and Steurer (STOC'17). The dependence is essentially tight for inverse-linear gap under the Exponential-Time Hypothesis, matching hardness from QMA(2) protocols. Second, for the matrix 2→4 norm, degree-O(n/ε) SoS gives a multiplicative (1+ε) approximation. Barak et al. (STOC'12) previously gave a comparable-time constant-gap decision algorithm; our result gives a multiplicative guarantee and extends to a family of p→q norms with even q. Finally, for degree-d polynomial optimization, we recover the convergence theorem of Bhattiprolu et al. (FOCS'17) with a shorter, more direct proof: degree-k SoS gives approximation ratio Od((n/k)d/2−1).
The paper introduces no new relaxation. Instead, the high-moment argmax gives a common way to read an SoS solution, unifying previously separate convergence analyses and yielding sharper bounds or simpler proofs.
We answer two questions regarding the sum-of-squares for the SYK model left open in Ref. 1, both of which are related to graphs. First (a "limitation"), we show that a fragment of the sum-of-squares, in which one considers commutation relations of degree-4 Majorana operators but does not impose any other relations on them, does not give the correct order of magnitude bound on the ground state energy. Second (a "separation"), we show that the graph invariant Ψ(G) defined in Ref. 1 may be strictly larger than the independence number α(G). The invariant Ψ(G) is a bound on the norm of a Hamiltonian whose terms obey commutation relations determined by the graph G, and it was shown that α(G)≤Ψ(G)≤ϑ(G), where ϑ(⋅) is the Lovasz theta function. We briefly discuss the case of q=4 in the SYK model. Separately, we define a problem that we call the quantum knapsack problem.