Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number

Authors Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.42.pdf
  • Filesize: 0.57 MB
  • 7 pages

Document Identifiers

Author Details

Venkatesan Guruswami
  • University of California Berkeley, CA, USA
Pravesh K. Kothari
  • Carnegie Mellon University, Pittsburgh, PA, USA
Peter Manohar
  • Carnegie Mellon University, Pittsburgh, PA, USA

Cite AsGet BibTex

Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar. Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 42:1-42:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.42

Abstract

Let H(k,n,p) be the distribution on k-uniform hypergraphs where every subset of [n] of size k is included as an hyperedge with probability p independently. In this work, we design and analyze a simple spectral algorithm that certifies a bound on the size of the largest clique, ω(H), in hypergraphs H ∼ H(k,n,p). For example, for any constant p, with high probability over the choice of the hypergraph, our spectral algorithm certifies a bound of Õ(√n) on the clique number in polynomial time. This matches, up to polylog(n) factors, the best known certificate for the clique number in random graphs, which is the special case of k = 2. Prior to our work, the best known refutation algorithms [Amin Coja-Oghlan et al., 2004; Sarah R. Allen et al., 2015] rely on a reduction to the problem of refuting random k-XOR via Feige’s XOR trick [Uriel Feige, 2002], and yield a polynomially worse bound of Õ(n^{3/4}) on the clique number when p = O(1). Our algorithm bypasses the XOR trick and relies instead on a natural generalization of the Lovász theta semidefinite programming relaxation for cliques in hypergraphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Planted clique
  • Average-case complexity
  • Spectral refutation
  • Random matrix theory

Metrics

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

References

  1. Sarah R. Allen, Ryan O'Donnell, and David Witmer. How to refute a random CSP. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, pages 689-708, 2015. Google Scholar
  2. Noga Alon, Michael Krivelevich, and Benny Sudakov. Finding a large hidden clique in a random graph. In SODA, pages 594-598. ACM/SIAM, 1998. Google Scholar
  3. Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, and Aaron Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem. In FOCS, pages 428-437. IEEE Computer Society, 2016. Google Scholar
  4. Amin Coja-Oghlan, Andreas Goerdt, and André Lanka. Strong refutation heuristics for random k-sat. In Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques, volume 3122 of Lecture Notes in Computer Science, pages 310-321. Springer, 2004. Google Scholar
  5. Yash Deshpande and Andrea Montanari. Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems. In COLT, volume 40 of JMLR Workshop and Conference Proceedings, pages 523-562. JMLR.org, 2015. Google Scholar
  6. Uriel Feige. Relations between average case complexity and approximation complexity. In STOC, pages 534-543. ACM, 2002. Google Scholar
  7. Uriel Feige and Robert Krauthgamer. Finding and certifying a large hidden clique in a semirandom graph. Random Struct. Algorithms, 16(2):195-208, 2000. Google Scholar
  8. Uriel Feige and Robert Krauthgamer. The probable value of the lovász-schrijver relaxations for maximum independent set. SIAM J. Comput., 32(2):345-370, 2003. Google Scholar
  9. 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. CoRR, abs/1507.05230, 2015. Google Scholar
  10. Mark Jerrum. Large cliques elude the metropolis process. Random Struct. Algorithms, 3(4):347-360, 1992. Google Scholar
  11. Michael Krivelevich and Benny Sudakov. The chromatic numbers of random hypergraphs. Random Struct. Algorithms, 12(4):381-403, 1998. Google Scholar
  12. Ludek Kucera. Expected complexity of graph partitioning problems. Discrete Applied Mathematics, 57(2-3):193-212, 1995. Google Scholar
  13. Raghu Meka, Aaron Potechin, and Avi Wigderson. Sum-of-squares lower bounds for planted clique. In STOC, pages 87-96. ACM, 2015. Google Scholar
  14. Prasad Raghavendra and Tselil Schramm. Tight lower bounds for planted clique in the degree-4 SOS program. CoRR, abs/1507.05136, 2015. Google Scholar
  15. Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4):389-434, August 2012. URL: https://doi.org/10.1007/s10208-011-9099-z.
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