Document Open Access Logo

SOS Lower Bound for Exact Planted Clique

Author Shuo Pang

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2021.26.pdf
  • Filesize: 1.23 MB
  • 63 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Proof complexity
  • Mathematics of computing → Random graphs
  • Theory of computation → Semidefinite programming
Keywords
  • Sum-of-Squares
  • planted clique
  • random graphs
  • average-case lower bound

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We prove a SOS degree lower bound for the planted clique problem on the Erdös-Rényi random graph G(n,1/2). The bound we get is degree d = Ω(ε²log n/log log n) for clique size ω = n^{1/2-ε}, which is almost tight. This improves the result of [Barak et al., 2019] for the "soft" version of the problem, where the family of the equality-axioms generated by x₁+...+x_n = ω is relaxed to one inequality x₁+...+x_n ≥ ω.
As a technical by-product, we also "naturalize" certain techniques that were developed and used for the relaxed problem. This includes a new way to define the pseudo-expectation, and a more robust method to solve out the coarse diagonalization of the moment matrix.

Cite As Get BibTex

Shuo Pang. SOS Lower Bound for Exact Planted Clique. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 26:1-26:63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CCC.2021.26

Author Details

Shuo Pang
  • Mathematics Department, University of Chicago, IL, USA

Acknowledgements

I am very grateful to Aaron Potechin for the introduction of the problem and the encouraging communications, and to Alexander Razborov for the advice and help on improving the quality of the paper. My thanks also go to the anonymous reviewers for their constructive criticism of the presentation.

References

  1. Noga Alon, Michael Krivelevich, and Benny Sudakov. Finding a large hidden clique in a random graph. Random Structures & Algorithms, 13(3-4):457-466, 1998. Google Scholar
  2. Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 171-180, 2010. Google Scholar
  3. Sanjeev Arora, Boaz Barak, Markus Brunnermeier, and Rong Ge. Computational complexity and information asymmetry in financial products. Communications of the ACM, 54(5):101-107, 2011. Google Scholar
  4. Boaz Barak, Fernando GSL Brandao, Aram W Harrow, Jonathan Kelner, David Steurer, and Yuan Zhou. Hypercontractivity, sum-of-squares proofs, and their applications. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 307-326, 2012. Google Scholar
  5. Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem. SIAM Journal on Computing, 48(2):687-735, 2019. Google Scholar
  6. Boaz Barak and David Steurer. Sum-of-squares proofs and the quest toward optimal algorithms. In Proceedings of International Congress of Mathematicians (ICM), 2014. Google Scholar
  7. Paul Beame, Russell Impagliazzo, Jan Krajíček, Toniann Pitassi, and Pavel Pudlák. Lower bounds on hilbert’s nullstellensatz and propositional proofs. Proceedings of the London Mathematical Society, 3(1):1-26, 1996. Google Scholar
  8. Quentin Berthet and Philippe Rigollet. Complexity theoretic lower bounds for sparse principal component detection. In Conference on Learning Theory, pages 1046-1066. PMLR, 2013. Google Scholar
  9. P Delsarte. An algebraic approach to association schemes of coding theory, phillips j, 1973. Google Scholar
  10. Yash Deshpande and Andrea Montanari. Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems. In Conference on Learning Theory, pages 523-562. PMLR, 2015. Google Scholar
  11. Fernando Escalante. Schnittverbände in graphen. In Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, volume 38, pages 199-220. Springer, 1972. Google Scholar
  12. Uriel Feige and Robert Krauthgamer. Finding and certifying a large hidden clique in a semirandom graph. Random Structures & Algorithms, 16(2):195-208, 2000. Google Scholar
  13. Uriel Feige and Robert Krauthgamer. The probable value of the lovász-schrijver relaxations for maximum independent set. SIAM Journal on Computing, 32(2):345-370, 2003. Google Scholar
  14. Dima Grigoriev and Nicolai Vorobjov. Complexity of null-and positivstellensatz proofs. Annals of Pure and Applied Logic, 113(1-3):153-160, 2001. Google Scholar
  15. Samuel B Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, and Tselil Schramm. On the integrality gap of degree-4 sum of squares for planted clique. ACM Transactions on Algorithms (TALG), 14(3):1-31, 2018. Google Scholar
  16. Samuel B Hopkins, Pravesh K Kothari, and Aaron Potechin. Sos and planted clique: Tight analysis of mpw moments at all degrees and an optimal lower bound at degree four. arXiv preprint, 2015. URL: http://arxiv.org/abs/1507.05230.
  17. Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer. The power of sum-of-squares for detecting hidden structures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 720-731. IEEE, 2017. Google Scholar
  18. Mark Jerrum. Large cliques elude the metropolis process. Random Structures & Algorithms, 3(4):347-359, 1992. Google Scholar
  19. R Karp. Probabilistic analysis of some combinatorial search problems. traub, jf (ed.): Algorithms and complexity: New directions and recent results, 1976. Google Scholar
  20. Pravesh Kothari, Ryan O'Donnell, and Tselil Schramm. Sos lower bounds with hard constraints: think global, act local. arXiv preprint, 2018. URL: http://arxiv.org/abs/1809.01207.
  21. Pravesh K Kothari and Ruta Mehta. Sum-of-squares meets nash: Optimal lower bounds for finding any equilibrium. arXiv preprint, 2018. URL: http://arxiv.org/abs/1806.09426.
  22. Luděk Kučera. Expected complexity of graph partitioning problems. Discrete Applied Mathematics, 57(2-3):193-212, 1995. Google Scholar
  23. Jean B Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on optimization, 11(3):796-817, 2001. Google Scholar
  24. Dhruv Medarametla and Aaron Potechin. Bounds on the norms of uniform low degree graph matrices. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  25. Raghu Meka, Aaron Potechin, and Avi Wigderson. Sum-of-squares lower bounds for planted clique. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 87-96, 2015. Google Scholar
  26. Ryan O'Donnell. Sos is not obviously automatizable, even approximately. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  27. Pablo A Parrilo. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, California Institute of Technology, 2000. Google Scholar
  28. Pavel A Pevzner, Sing-Hoi Sze, et al. Combinatorial approaches to finding subtle signals in dna sequences. In ISMB, volume 8, pages 269-278, 2000. Google Scholar
  29. Prasad Raghavendra and Benjamin Weitz. On the bit complexity of sum-of-squares proofs. arXiv preprint, 2017. URL: http://arxiv.org/abs/1702.05139.
  30. Naum Z Shor. Class of global minimum bounds of polynomial functions. Cybernetics, 23(6):731-734, 1987. Google Scholar
  31. Evgenij E Tyrtyshnikov. How bad are hankel matrices? Numerische Mathematik, 67(2):261-269, 1994. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact