2026-07-23T20:16:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18300 2024-03-06T11:01:33Z ddc:004 open_access

A Degree 4 Sum-Of-Squares Lower Bound for the Clique Number of the Paley Graph Kunisky, Dmitriy Yu, Xifan convex optimization sum of squares Paley graph derandomization We prove that the degree 4 sum-of-squares (SOS) relaxation of the clique number of the Paley graph on a prime number p of vertices has value at least Ω(p^{1/3}). This is in contrast to the widely believed conjecture that the actual clique number of the Paley graph is O(polylog(p)). Our result may be viewed as a derandomization of that of Deshpande and Montanari (2015), who showed the same lower bound (up to polylog(p) terms) with high probability for the Erdős-Rényi random graph on p vertices, whose clique number is with high probability O(log(p)). We also show that our lower bound is optimal for the Feige-Krauthgamer construction of pseudomoments, derandomizing an argument of Kelner. Finally, we present numerical experiments indicating that the value of the degree 4 SOS relaxation of the Paley graph may scale as O(p^{1/2 - ε}) for some ε > 0, and give a matrix norm calculation indicating that the pseudocalibration construction for SOS lower bounds for random graphs will not immediately transfer to the Paley graph. Taken together, our results suggest that degree 4 SOS may break the "√p barrier" for upper bounds on the clique number of Paley graphs, but prove that it can at best improve the exponent from 1/2 to 1/3. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dmitriy Kunisky and Xifan Yu 2023 Is Part Of LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2023.30 urn:nbn:de:0030-drops-183008 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.30 eng https://creativecommons.org/licenses/by/4.0/legalcode