Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

SoS certification for symmetric quadratic functions and its connection to constrained boolean hypercube optimization

Adam Kurpisz, Aaron Henry Potechin, Elias Wirth

Published Jan 1, 2021• 0 citations
Publisher

Abstract

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.

DOI
10.3929/ethz-b-000507054

Related papers

On the Sum-of-Squares Degree of Symmetric Quadratic Functions

Troy Lee, Anupam Prakash, Ronald de Wolf +1 more

We study how well functions over the boolean hypercube of the form $f_k(x)=(|x|-k)(|x|-k-1)$ can be approximated by sums of squares of low-degree polynomials, obtaining good bounds for the case of approximation in $\ell_{\infty}$-norm as well as in $\ell_1$-norm. We describe three complexity-theoretic applications: (1) a proof that the recent breakthrough lower bound of Lee, Raghavendra, and Steurer on the positive semidefinite extension complexity of the correlation and TSP polytopes cannot be improved further by showing better sum-of-squares degree lower bounds on $\ell_1$-approximation of $f_k$; (2) a proof that Grigoriev's lower bound on the degree of Positivstellensatz refutations for the knapsack problem is optimal, answering an open question from his work; (3) bounds on the query complexity of quantum algorithms whose expected output approximates such functions.

arXiv:1601.02311•Leibniz international proceedings in informatics•Jan 1, 2016•17 citations

High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts

Monaldo Mastrolilli

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.

arXiv:1709.07966•SIAM Journal on Optimization•Jan 1, 2020•3 citations

On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank

Adam Kurpisz, Lucas Slot, Mikhail S. Zaytsev

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.

arXiv:2605.00594•International Symposium on Symbolic and Algebraic Computation•Jul 9, 2026•0 citations

On the Rational Degree of Boolean Functions and Applications

Vishnu Iyer, Siddhartha Jain, Robin Kothari +5 more

We study a natural complexity measure of Boolean functions known as the rational degree. Denoted $\textrm{rdeg}(f)$, it is the minimal degree of a rational function that is equal to $f$ on the Boolean hypercube. For total functions $f$, it is conjectured that $\textrm{rdeg}(f)$ is polynomially related to the Fourier degree of $f$, $\textrm{deg}(f)$. Towards this conjecture, we show that: - Symmetric functions have rational degree at least $Ω(\textrm{deg}(f))$ and unate functions have rational degree at least $\sqrt{\textrm{deg}(f)}$. We observe that both of these lower bounds are asymptotically tight. - Read-once AC and TC formulae have rational degree at least $Ω(\sqrt{\textrm{deg}(f)})$. If these formulae contain parity gates, we show a lower bound of $Ω(\textrm{deg}(f)^{1/2d})$, where $d$ is the depth. - Almost every Boolean function on $n$ variables has rational degree at least $n/2 - O(\sqrt{n})$. In contrast, we exhibit partial functions that witness unbounded separations between rational and approximate degree, in both directions. As a consequence, we show that for quantum computers, post-selection and bounded-error are incomparable resources in the black-box model. In addition, we show AND and OR composition lemmas for the rational degree and exhibit new polynomial separations between the rational degree and other well-studied complexity measures, such as sensitivity and spectral sensitivity.

arXiv:2310.08004•Oct 12, 2023•4 citations

Classical Lower Bounds from Quantum Upper Bounds

Shalev Ben-David, Adam Bouland, Ankit Garg +1 more

We prove lower bounds on complexity measures, such as the approximate degree of a Boolean function and the approximate rank of a Boolean matrix, using quantum arguments. We prove these lower bounds using a quantum query algorithm for the combinatorial group testing problem. We show that for any function f, the approximate degree of computing the OR of n copies of f is Omega(sqrt n) times the approximate degree of f, which is optimal. No such general result was known prior to our work, and even the lower bound for the OR of ANDs function was only resolved in 2013. We then prove an analogous result in communication complexity, showing that the logarithm of the approximate rank (or more precisely, the approximate gamma-2 norm) of F: X x Y to 0,1 grows by a factor of Omega (sqrtn) when we take the OR of n copies of F, which is also essentially optimal. As a corollary, we give a new proof of Razborov's celebrated Omega(sqrtn) lower bound on the quantum communication complexity of the disjointness problem. Finally, we generalize both these results from composition with the OR function to composition with arbitrary symmetric functions, yielding nearly optimal lower bounds in this setting as well.

Annual Symposium on Foundations of Computer Science•Oct 1, 2018•17 citations

Quadratizations of symmetric pseudo-Boolean functions: sub-linear bounds on the number of auxiliary variables

Endre Boros, Yves Crama, Elisabeth Rodríguez-Heck

The problem of minimizing a pseudo-Boolean function with no additional constraints arises in a variety of applications.A quadratization is a quadratic reformulation of the nonlinear problem obtained by introducing a set of auxiliary binary variables which can be optimized using quadratic optimization techniques.Using the well-known result that a pseudo-Boolean function can be uniquely expressed as a multilinear polynomial, any pseudo-Boolean function can be quadratized by providing a quadratization for negative monomials and one for positive monomials.A desirable property for a quadratization is to introduce small number of auxiliary variables.For the case of negative monomials there exists a quadratization using a single auxiliary variable which is, in addition, submodular.However, much less is known for positive monomials.The best lower bound on the number of variables required by a quadratization in the literature is n-1 2 .We present here new quadratizations of the positive monomial that significantly improve this lower bound decreasing it to a logarithmic bound.This lower bound is derived from a more general result, stating that a quadratization with a logarithmic number of variables can be defined for exact kout-of-n functions, which is a more general class of symmetric functions.Moreover, for exact k-out-of-n functions we also prove that a logarithmic number of variables is necessary when requiring certain symmetry conditions to the quadratization.Finally, we provide quadratizations for general symmetric functions using O( √ n) auxiliary variables.This upper bound nicely matches a lower bound of Ω( √ n) variables that was recently introduced.

ISAIM•Jan 4, 2018•7 citations
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.
We study how well functions over the boolean hypercube of the form fk(x)=(∣x∣−k)(∣x∣−k−1)f_k(x)=(|x|-k)(|x|-k-1)fk​(x)=(∣x∣−k)(∣x∣−k−1) can be approximated by sums of squares of low-degree polynomials, obtaining good bounds for the case of approximation in ℓ∞\ell_{\infty}ℓ∞​-norm as well as in ℓ1\ell_1ℓ1​-norm. We describe three complexity-theoretic applications: (1) a proof that the recent breakthrough lower bound of Lee, Raghavendra, and Steurer on the positive semidefinite extension complexity of the correlation and TSP polytopes cannot be improved further by showing better sum-of-squares degree lower bounds on ℓ1\ell_1ℓ1​-approximation of fkf_kfk​; (2) a proof that Grigoriev's lower bound on the degree of Positivstellensatz refutations for the knapsack problem is optimal, answering an open question from his work; (3) bounds on the query complexity of quantum algorithms whose expected output approximates such functions.
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 analyze the sum-of-squares rank of unweighted instances of the Minimum Knapsack (MK) problem, i.e., minimization of ∑i=1nxi\sum _{i=1}^n x_i∑i=1n​xi​ for 0/1 variables under the constraint ∑i=1nxi≥q\sum _{i=1}^n x_i \ge q∑i=1n​xi​≥q, with q∈Rq \in \mathbb {R}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 sublinear rank O(n)O(\sqrt {n})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 < 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 study a natural complexity measure of Boolean functions known as the rational degree. Denoted rdeg(f)\textrm{rdeg}(f)rdeg(f), it is the minimal degree of a rational function that is equal to fff on the Boolean hypercube. For total functions fff, it is conjectured that rdeg(f)\textrm{rdeg}(f)rdeg(f) is polynomially related to the Fourier degree of fff, deg(f)\textrm{deg}(f)deg(f). Towards this conjecture, we show that: - Symmetric functions have rational degree at least Ω(deg(f))Ω(\textrm{deg}(f))Ω(deg(f)) and unate functions have rational degree at least deg(f)\sqrt{\textrm{deg}(f)}deg(f)​. We observe that both of these lower bounds are asymptotically tight. - Read-once AC and TC formulae have rational degree at least Ω(deg(f))Ω(\sqrt{\textrm{deg}(f)})Ω(deg(f)​). If these formulae contain parity gates, we show a lower bound of Ω(deg(f)1/2d)Ω(\textrm{deg}(f)^{1/2d})Ω(deg(f)1/2d), where ddd is the depth. - Almost every Boolean function on nnn variables has rational degree at least n/2−O(n)n/2 - O(\sqrt{n})n/2−O(n​). In contrast, we exhibit partial functions that witness unbounded separations between rational and approximate degree, in both directions. As a consequence, we show that for quantum computers, post-selection and bounded-error are incomparable resources in the black-box model. In addition, we show AND and OR composition lemmas for the rational degree and exhibit new polynomial separations between the rational degree and other well-studied complexity measures, such as sensitivity and spectral sensitivity.
We prove lower bounds on complexity measures, such as the approximate degree of a Boolean function and the approximate rank of a Boolean matrix, using quantum arguments. We prove these lower bounds using a quantum query algorithm for the combinatorial group testing problem. We show that for any function f, the approximate degree of computing the OR of n copies of f is Omega(sqrt n) times the approximate degree of f, which is optimal. No such general result was known prior to our work, and even the lower bound for the OR of ANDs function was only resolved in 2013. We then prove an analogous result in communication complexity, showing that the logarithm of the approximate rank (or more precisely, the approximate gamma-2 norm) of F: X x Y to 0,1 grows by a factor of Omega (sqrtn) when we take the OR of n copies of F, which is also essentially optimal. As a corollary, we give a new proof of Razborov's celebrated Omega(sqrtn) lower bound on the quantum communication complexity of the disjointness problem. Finally, we generalize both these results from composition with the OR function to composition with arbitrary symmetric functions, yielding nearly optimal lower bounds in this setting as well.
The problem of minimizing a pseudo-Boolean function with no additional constraints arises in a variety of applications.A quadratization is a quadratic reformulation of the nonlinear problem obtained by introducing a set of auxiliary binary variables which can be optimized using quadratic optimization techniques.Using the well-known result that a pseudo-Boolean function can be uniquely expressed as a multilinear polynomial, any pseudo-Boolean function can be quadratized by providing a quadratization for negative monomials and one for positive monomials.A desirable property for a quadratization is to introduce small number of auxiliary variables.For the case of negative monomials there exists a quadratization using a single auxiliary variable which is, in addition, submodular.However, much less is known for positive monomials.The best lower bound on the number of variables required by a quadratization in the literature is n-1 2 .We present here new quadratizations of the positive monomial that significantly improve this lower bound decreasing it to a logarithmic bound.This lower bound is derived from a more general result, stating that a quadratization with a logarithmic number of variables can be defined for exact kout-of-n functions, which is a more general class of symmetric functions.Moreover, for exact k-out-of-n functions we also prove that a logarithmic number of variables is necessary when requiring certain symmetry conditions to the quadratization.Finally, we provide quadratizations for general symmetric functions using O( √ n) auxiliary variables.This upper bound nicely matches a lower bound of Ω( √ n) variables that was recently introduced.