License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.90
URN: urn:nbn:de:0030-drops-141595
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14159/
Go to the corresponding LIPIcs Volume Portal

Kurpisz, Adam ; Potechin, Aaron ; Wirth, Elias Samuel

SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization

pdf-format:
LIPIcs-ICALP-2021-90.pdf (0.8 MB)

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(√nlog(n)) SoS certificate for this problem.

BibTeX - Entry

@InProceedings{kurpisz_et_al:LIPIcs.ICALP.2021.90,
  author =	{Kurpisz, Adam and Potechin, Aaron and Wirth, Elias Samuel},
  title =	{{SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{90:1--90:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14159},
  URN =		{urn:nbn:de:0030-drops-141595},
  doi =		{10.4230/LIPIcs.ICALP.2021.90},
  annote =	{Keywords: symmetric quadratic functions, SoS certificate, hypercube optimization, semidefinite programming}
}

Keywords: symmetric quadratic functions, SoS certificate, hypercube optimization, semidefinite programming
Collection: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue Date: 2021
Date of publication: 02.07.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI