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.ITCS.2017.59
URN: urn:nbn:de:0030-drops-81980
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8198/
Go to the corresponding LIPIcs Volume Portal

O'Donnell, Ryan

SOS Is Not Obviously Automatizable, Even Approximately

pdf-format:
LIPIcs-ITCS-2017-59.pdf (0.5 MB)

Abstract

Suppose we want to minimize a polynomial p(x) = p(x_1,...,x_n), subject to some polynomial constraints q_1(x),...,q_m(x) >_ 0, using the Sum-of-Squares (SOS) SDP hierarachy. Assume we are in the "explicitly bounded" ("Archimedean") case where the constraints include x_i^2 <_ 1 for all 1 <_ i <_ n. It is often stated that the degree-d version of the SOS hierarchy can be solved, to
high accuracy, in time n^O(d). Indeed, I myself have stated this in several previous works.

The point of this note is to state (or remind the reader) that this is not obviously true. The difficulty comes not from the "r" in the Ellipsoid Algorithm, but from the "R"; a priori, we only know an exponential upper bound on the number of bits needed to write down the SOS solution. An explicit example is given of a degree-2 SOS program illustrating the difficulty.

BibTeX - Entry

@InProceedings{odonnell:LIPIcs:2017:8198,
  author =	{Ryan O'Donnell},
  title =	{{SOS Is Not Obviously Automatizable, Even Approximately}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{59:1--59:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Christos H. Papadimitriou},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8198},
  URN =		{urn:nbn:de:0030-drops-81980},
  doi =		{10.4230/LIPIcs.ITCS.2017.59},
  annote =	{Keywords: Sum-of-Squares, semidefinite programming}
}

Keywords: Sum-of-Squares, semidefinite programming
Collection: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Issue Date: 2017
Date of publication: 28.11.2017

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