Document Open Access Logo

Is the Space Complexity of Planted Clique Recovery the Same as That of Detection?

Author Jay Mardia

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.34.pdf
  • Filesize: 0.64 MB
  • 17 pages

Document Identifiers

Author Details

Jay Mardia
  • Department of Electrical Engineering, Stanford University, CA, USA

Funding

This work was supported by a Robert Bosch Stanford Graduate Fellowship.

Acknowledgements

We would like to thank Dean Doron, Gábor Lugosi, and Kevin Tian for helpful discussions and pointers to relevant literature.

Cite AsGet BibTex

Jay Mardia. Is the Space Complexity of Planted Clique Recovery the Same as That of Detection?. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITCS.2021.34

Abstract

We study the planted clique problem in which a clique of size k is planted in an Erdős-Rényi graph G(n, 1/2), and one is interested in either detecting or recovering this planted clique. This problem is interesting because it is widely believed to show a statistical-computational gap at clique size k = Θ(√n), and has emerged as the prototypical problem with such a gap from which average-case hardness of other statistical problems can be deduced. It also displays a tight computational connection between the detection and recovery variants, unlike other problems of a similar nature. This wide investigation into the computational complexity of the planted clique problem has, however, mostly focused on its time complexity. To begin investigating the robustness of these statistical-computational phenomena to changes in our notion of computational efficiency, we ask- Do the statistical-computational phenomena that make the planted clique an interesting problem also hold when we use "space efficiency" as our notion of computational efficiency? It is relatively easy to show that a positive answer to this question depends on the existence of a O(log n) space algorithm that can recover planted cliques of size k = Ω(√n). Our main result comes very close to designing such an algorithm. We show that for k = Ω(√n), the recovery problem can be solved in O((log^*{n}-log^*{k/(√n}) ⋅ log n) bits of space. 1) If k = ω(√nlog^{(𝓁)}n) for any constant integer 𝓁 > 0, the space usage is O(log n) bits. 2) If k = Θ(√n), the space usage is O(log^* n ⋅ log n) bits. Our result suggests that there does exist an O(log n) space algorithm to recover cliques of size k = Ω(√n), since we come very close to achieving such parameters. This provides evidence that the statistical-computational phenomena that (conjecturally) hold for planted clique time complexity also (conjecturally) hold for space complexity. Due to space limitations, we omit proofs from this manuscript. The entire paper with full proofs can be found on arXiv at https://arxiv.org/abs/2008.12825.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Statistical computational gaps
  • Planted clique
  • Space complexity
  • Average case computational complexity

Metrics

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

Related Versions

References

  1. Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):6446-6531, 2017. Google Scholar
  2. Emmanuel Abbe and Colin Sandon. Achieving the ks threshold in the general stochastic block model with linearized acyclic belief propagation. In Advances in Neural Information Processing Systems, pages 1334-1342, 2016. Google Scholar
  3. Dimitris Achlioptas and Amin Coja-Oghlan. Algorithmic barriers from phase transitions. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 793-802. IEEE, 2008. Google Scholar
  4. Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, and Ning Xie. Testing k-wise and almost k-wise independence. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 496-505, 2007. Google Scholar
  5. 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
  6. Brendan PW Ames and Stephen A Vavasis. Nuclear norm minimization for the planted clique and biclique problems. Mathematical programming, 129(1):69-89, 2011. Google Scholar
  7. Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. Google Scholar
  8. Sivaraman Balakrishnan, Simon S Du, Jerry Li, and Aarti Singh. Computationally efficient robust sparse estimation in high dimensions. In Conference on Learning Theory, pages 169-212, 2017. Google Scholar
  9. 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
  10. Quentin Berthet and Philippe Rigollet. Complexity theoretic lower bounds for sparse principal component detection. In Shai Shalev-Shwartz and Ingo Steinwart, editors, Proceedings of Machine Learning Research, volume 30, pages 1046-1066, Princeton, NJ, USA, 12-14 Jun 2013. PMLR. URL: http://proceedings.mlr.press/v30/Berthet13.html.
  11. B Bollobas and P Erdös. Cliques in random graphs. MPCPS, 80(3):419, 1976. Google Scholar
  12. Matthew Brennan and Guy Bresler. Reducibility and statistical-computational gaps from secret leakage. arXiv preprint, 2020. URL: http://arxiv.org/abs/2005.08099.
  13. Matthew Brennan, Guy Bresler, and Wasim Huleihel. Reducibility and computational lower bounds for problems with planted sparse structure. arXiv preprint, 2018. URL: http://arxiv.org/abs/1806.07508.
  14. Yudong Chen and Jiaming Xu. Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices. arXiv preprint, 2014. URL: http://arxiv.org/abs/1402.1267.
  15. Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E, 84(6):066106, 2011. Google Scholar
  16. Yael Dekel, Ori Gurel-Gurevich, and Yuval Peres. Finding hidden cliques in linear time with high probability. Combinatorics, Probability and Computing, 23(1):29-49, 2014. Google Scholar
  17. Yash Deshpande and Andrea Montanari. Finding hidden cliques of size √N/e in nearly linear time. Foundations of Computational Mathematics, 15(4):1069-1128, 2015. Google Scholar
  18. 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, 2015. Google Scholar
  19. David Dobkin, Richard J Lipton, and Steven Reiss. Linear programming is log-space hard for p. Information Processing Letters, 8(2):96-97, 1979. Google Scholar
  20. 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
  21. 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
  22. Uriel Feige and Dorit Ron. Finding hidden cliques in linear time. In 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), pages 189-204. Discrete Mathematics and Theoretical Computer Science, 2010. Google Scholar
  23. Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao. Statistical algorithms and a lower bound for detecting planted cliques. Journal of the ACM (JACM), 64(2):1-37, 2017. Google Scholar
  24. David Gamarnik and Ilias Zadik. The landscape of the planted clique problem: Dense subgraphs and the overlap gap property. arXiv preprint, 2019. URL: http://arxiv.org/abs/1904.07174.
  25. Bruce Hajek, Yihong Wu, and Jiaming Xu. Computational lower bounds for community detection on random graphs. In Conference on Learning Theory, pages 899-928, 2015. Google Scholar
  26. 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
  27. 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
  28. Samuel B Hopkins and David Steurer. Bayesian estimation from few samples: community detection and related problems. arXiv preprint, 2017. URL: http://arxiv.org/abs/1710.00264.
  29. Samuel Brink Klevit Hopkins. Statistical inference and the sum of squares method. PhD thesis, Cornell University, 2018. Google Scholar
  30. Mark Jerrum. Large cliques elude the metropolis process. Random Structures & Algorithms, 3(4):347-359, 1992. Google Scholar
  31. Pravesh K Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer. Sum of squares lower bounds for refuting any csp. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 132-145, 2017. Google Scholar
  32. Luděk Kučera. Expected complexity of graph partitioning problems. Discrete Applied Mathematics, 57(2-3):193-212, 1995. Google Scholar
  33. Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. arXiv preprint, 2019. URL: http://arxiv.org/abs/1907.11636.
  34. Thibault Lesieur, Florent Krzakala, and Lenka Zdeborová. Phase transitions in sparse pca. In 2015 IEEE International Symposium on Information Theory (ISIT), pages 1635-1639. IEEE, 2015. Google Scholar
  35. Jerry Li. Robust sparse estimation tasks in high dimensions. arXiv preprint, 2017. URL: http://arxiv.org/abs/1702.05860.
  36. Gábor Lugosi. Lectures on combinatorial statistics. 47th Probability Summer School, Saint-Flour, pages 1-91, 2017. Google Scholar
  37. Jay Mardia, Hilal Asi, and Kabir Aladin Chandrasekher. Finding planted cliques in sublinear time. arXiv preprint, 2020. URL: http://arxiv.org/abs/2004.12002.
  38. Laurent Massoulié. Community detection thresholds and the weak ramanujan property. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 694-703, 2014. Google Scholar
  39. 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
  40. Elchanan Mossel, Joe Neeman, and Allan Sly. Consistency thresholds for the planted bisection model. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 69-75, 2015. Google Scholar
  41. Miklós Z Rácz and Benjamin Schiffer. Finding a planted clique by adaptive probing. arXiv preprint, 2019. URL: http://arxiv.org/abs/1903.12050.
  42. Emile Richard and Andrea Montanari. A statistical model for tensor pca. In Advances in Neural Information Processing Systems, pages 2897-2905, 2014. Google Scholar
  43. Benjamin Rossman. On the constant-depth complexity of k-clique. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 721-730, 2008. Google Scholar
  44. Benjamin Rossman. The monotone complexity of k-clique on random graphs. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 193-201. IEEE, 2010. Google Scholar
  45. Michael Saks. Randomization and derandomization in space-bounded computation. In Proceedings of Computational Complexity (Formerly Structure in Complexity Theory), pages 128-149. IEEE, 1996. Google Scholar
  46. Tselil Schramm and Alexander S Wein. Computational barriers to estimation from low-degree polynomials. arXiv preprint, 2020. URL: http://arxiv.org/abs/2008.02269.
  47. Maria Serna. Approximating linear programming is log-space complete for p. Information Processing Letters, 37(4):233-236, 1991. Google Scholar
  48. Avi Wigderson. Mathematics and Computation: A Theory Revolutionizing Technology and Science. Princeton University Press, 2019. 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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact