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.2019.61
URN: urn:nbn:de:0030-drops-101545
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10154/
Potechin, Aaron
Sum of Squares Lower Bounds from Symmetry and a Good Story
Abstract
In this paper, we develop machinery which makes it much easier to prove sum of squares lower bounds when the problem is symmetric under permutations of [1,n] and the unsatisfiability of our problem comes from integrality arguments, i.e. arguments that an expression must be an integer. Roughly speaking, to prove SOS lower bounds with our machinery it is sufficient to verify that the answer to the following three questions is yes:
1) Are there natural pseudo-expectation values for the problem?
2) Are these pseudo-expectation values rational functions of the problem parameters?
3) Are there sufficiently many values of the parameters for which these pseudo-expectation values correspond to the actual expected values over a distribution of solutions which is the uniform distribution over permutations of a single solution?
We demonstrate our machinery on three problems, the knapsack problem analyzed by Grigoriev, the MOD 2 principle (which says that the complete graph K_n has no perfect matching when n is odd), and the following Turan type problem: Minimize the number of triangles in a graph G with a given edge density. For knapsack, we recover Grigoriev's lower bound exactly. For the MOD 2 principle, we tighten Grigoriev's linear degree sum of squares lower bound, making it exact. Finally, for the triangle problem, we prove a sum of squares lower bound for finding the minimum triangle density. This lower bound is completely new and gives a simple example where constant degree sum of squares methods have a constant factor error in estimating graph densities.
BibTeX - Entry
@InProceedings{potechin:LIPIcs:2018:10154,
author = {Aaron Potechin},
title = {{Sum of Squares Lower Bounds from Symmetry and a Good Story}},
booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
pages = {61:1--61:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-095-8},
ISSN = {1868-8969},
year = {2018},
volume = {124},
editor = {Avrim Blum},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10154},
URN = {urn:nbn:de:0030-drops-101545},
doi = {10.4230/LIPIcs.ITCS.2019.61},
annote = {Keywords: Sum of squares hierarchy, proof complexity, graph theory, lower bounds}
}
|
Keywords: |
|
Sum of squares hierarchy, proof complexity, graph theory, lower bounds |
|
Collection: |
|
10th Innovations in Theoretical Computer Science Conference (ITCS 2019) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
08.01.2019 |
