License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2021.23
URN: urn:nbn:de:0030-drops-142978
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14297/
Kothari, Pravesh K. ;
Manohar, Peter
A Stress-Free Sum-Of-Squares Lower Bound for Coloring
Abstract
We prove that with high probability over the choice of a random graph G from the Erdős-Rényi distribution G(n, 1/2), a natural n^{O(ε² log n)}-time, degree O(ε² log n) sum-of-squares semidefinite program cannot refute the existence of a valid k-coloring 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 sum-of-squares 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 instance-preserving non-pointwise 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 Stress-Free Sum-Of-Squares Lower Bound for Coloring}},
booktitle = {36th Computational Complexity Conference (CCC 2021)},
pages = {23:1--23:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-193-1},
ISSN = {1868-8969},
year = {2021},
volume = {200},
editor = {Kabanets, Valentine},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14297},
URN = {urn:nbn:de:0030-drops-142978},
doi = {10.4230/LIPIcs.CCC.2021.23},
annote = {Keywords: Sum-of-Squares, Graph Coloring, Independent Set, Lower Bounds}
}
|
Keywords: |
|
Sum-of-Squares, Graph Coloring, Independent Set, Lower Bounds |
|
Collection: |
|
36th Computational Complexity Conference (CCC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
08.07.2021 |
