License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.79
URN: urn:nbn:de:0030-drops-106556
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10655/
Go to the corresponding LIPIcs Volume Portal

Kurpisz, Adam

Sum-Of-Squares Bounds via Boolean Function Analysis

pdf-format:
LIPIcs-ICALP-2019-79.pdf (0.5 MB)

Abstract

We introduce a method for proving bounds on the SoS rank based on Boolean Function Analysis and Approximation Theory. We apply our technique to improve upon existing results, thus making progress towards answering several open questions.
We consider two questions by Laurent. First, finding what is the SoS rank of the linear representation of the set with no integral points. We prove that the SoS rank is between ceil[n/2] and ceil[~ n/2 +sqrt{n log{2n}} ~]. Second, proving the bounds on the SoS rank for the instance of the Min Knapsack problem. We show that the SoS rank is at least Omega(sqrt{n}) and at most ceil[{n+ 4 ceil[sqrt{n} ~]}/2]. Finally, we consider the question by Bienstock regarding the instance of the Set Cover problem. For this problem we prove the SoS rank lower bound of Omega(sqrt{n}).

BibTeX - Entry

@InProceedings{kurpisz:LIPIcs:2019:10655,
  author =	{Adam Kurpisz},
  title =	{{Sum-Of-Squares Bounds via Boolean Function Analysis}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{79:1--79:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10655},
  URN =		{urn:nbn:de:0030-drops-106556},
  doi =		{10.4230/LIPIcs.ICALP.2019.79},
  annote =	{Keywords: SoS certificate, SoS rank, hypercube optimization, semidefinite programming}
}

Keywords: SoS certificate, SoS rank, hypercube optimization, semidefinite programming
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

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