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 pseudoexpectation values for the problem?
2) Are these pseudoexpectation values rational functions of the problem parameters?
3) Are there sufficiently many values of the parameters for which these pseudoexpectation 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:161:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770958},
ISSN = {18688969},
year = {2018},
volume = {124},
editor = {Avrim Blum},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10154},
URN = {urn:nbn:de:0030drops101545},
doi = {10.4230/LIPIcs.ITCS.2019.61},
annote = {Keywords: Sum of squares hierarchy, proof complexity, graph theory, lower bounds}
}
08.01.2019
Keywords: 

Sum of squares hierarchy, proof complexity, graph theory, lower bounds 
Seminar: 

10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Issue date: 

2018 
Date of publication: 

08.01.2019 