Abstract
We prove that with high probability over the choice of a random graph G from the ErdősRényi distribution G(n, 1/2), a natural n^{O(ε² log n)}time, degree O(ε² log n) sumofsquares semidefinite program cannot refute the existence of a valid kcoloring of G for k = n^{1/2 + ε}. Our result implies that the refutation guarantee of the basic semidefinite program (a close variant of the Lovász theta function) cannot be appreciably improved by a natural o(log n)degree sumofsquares strengthening, and this is tight up to a n^{o(1)} slack in k. To the best of our knowledge, this is the first lower bound for coloring G(n, 1/2) for even a single round strengthening of the basic SDP in any SDP hierarchy.
Our proof relies on a new variant of instancepreserving nonpointwise complete reduction within SoS from coloring a graph to finding large independent sets in it. Our proof is (perhaps surprisingly) short, simple and does not require complicated spectral norm bounds on random matrices with dependent entries that have been otherwise necessary in the proofs of many similar results [Boaz Barak et al., 2016; S. B. {Hopkins} et al., 2017; Dmitriy Kunisky and Afonso S. Bandeira, 2019; Mrinalkanti Ghosh et al., 2020; Mohanty et al., 2020].
Our result formally holds for a constraint system where vertices are allowed to belong to multiple color classes; we leave the extension to the formally stronger formulation of coloring, where vertices must belong to unique colors classes, as an outstanding open problem.
BibTeX  Entry
@InProceedings{kothari_et_al:LIPIcs.CCC.2021.23,
author = {Kothari, Pravesh K. and Manohar, Peter},
title = {{A StressFree SumOfSquares Lower Bound for Coloring}},
booktitle = {36th Computational Complexity Conference (CCC 2021)},
pages = {23:123:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771931},
ISSN = {18688969},
year = {2021},
volume = {200},
editor = {Kabanets, Valentine},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14297},
URN = {urn:nbn:de:0030drops142978},
doi = {10.4230/LIPIcs.CCC.2021.23},
annote = {Keywords: SumofSquares, Graph Coloring, Independent Set, Lower Bounds}
}
Keywords: 

SumofSquares, Graph Coloring, Independent Set, Lower Bounds 
Collection: 

36th Computational Complexity Conference (CCC 2021) 
Issue Date: 

2021 
Date of publication: 

08.07.2021 