arxiv: 2511.20376 · v5 · submitted 2025-11-25 · 💻 cs.DS

Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares

Andreas G\"obel , Janosch Ruff , Leon Schiller This is my paper

Pith reviewed 2026-05-17 04:52 UTC · model grok-4.3

classification 💻 cs.DS

keywords random intersection graphsclique recoverysum-of-squarescommunity detectionplanted cliquesrobust algorithmsexact recoveryapproximate recovery

0 comments

The pith

Sum-of-squares algorithms recover exact and approximate community structure in random intersection graphs with overlapping planted cliques when k greatly exceeds the square root of n log n, and they tolerate noise and edge corruptions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper develops the first efficient methods to recover multiple overlapping cliques that have been planted randomly into a graph. The generative process creates polynomially many cliques of size near k by letting each vertex join each clique independently according to a fixed probability, so that individual vertices can end up in many different cliques at once. Earlier work handled only the simpler case of disjoint cliques; the overlaps here make the recovery problem substantially harder. The new algorithms rely on the sum-of-squares hierarchy to certify and extract the planted communities, achieving both exact and approximate recovery while remaining effective under noise, monotone adversarial edge additions, and an optimal number of edge corruptions. The methods succeed whenever the clique size satisfies k much larger than the square root of n times log n.

Core claim

The central claim is that the sum-of-squares hierarchy yields the first efficient algorithms for recovering the community structure of random intersection graphs, delivering both exact and approximate recovery. These algorithms remain robust to noise, monotone adversaries, and an optimal number of edge corruptions, and they succeed whenever k ≫ √(n log n). The approach follows the proofs-to-algorithms framework by using an appropriate degree of the hierarchy to certify the planted structure under the model's density and overlap conditions.

What carries the argument

The sum-of-squares hierarchy of appropriate degree, used through the proofs-to-algorithms paradigm to produce a semidefinite program that certifies the identities of the planted overlapping cliques inside the random intersection graph.

If this is right

Exact recovery of every planted clique becomes possible once the size condition is met.
Approximate recovery of the overlapping community structure succeeds under the same density regime.
The algorithms continue to work correctly after a bounded number of arbitrary edge corruptions.
Robustness carries over to monotone adversaries that may add edges in any way that preserves the planted structure.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same certification technique might transfer to other random graph models that feature overlapping dense subgraphs rather than strict cliques.
The appearance of the square-root-of-n-log-n threshold hints at a possible information-theoretic barrier that could be confirmed by constructing matching lower bounds.
Practical implementations could test the method on synthetic networks that mimic social or biological data with known overlapping groups.

Load-bearing premise

The generative model plants the cliques independently with each vertex included according to probability δ, and the sum-of-squares program of suitable degree can be solved efficiently while still certifying the planted communities despite overlaps.

What would settle it

Generating random instances with k set near the square root of n log n and checking whether the sum-of-squares relaxation fails to output the correct communities or fails to certify them would directly test whether the claimed recovery threshold holds.

Figures

Figures reproduced from arXiv: 2511.20376 by Andreas G\"obel, Janosch Ruff, Leon Schiller.

**Figure 1.** Figure 1: Sketch for Algorithm 1: (left) The Bipartite subgraph 𝐻(𝑇) = 𝐺[(𝑈 \ 𝑆ℓ) ⊎ 𝑉] ∩ 𝑁𝐺(𝑇) is balanced shown in Lemma 4.11. (right) Sketch of step one of the proof of identifiability for our SoS-based proof of Theorem 1.7 and our refutation algorithm (Theorem 6.19). pseudo distributions, this implies that 𝑆𝑇 can only put a small number of vertices outside of 𝑉(ℬ𝑅), which is a preliminary concentration statement … view at source ↗

**Figure 2.** Figure 2: (a) Sketch of event ℰ𝑎,𝑏. Vertices 𝑆ℓ (yellow area) is the set of vertices with label ℓ. The set of vertices 𝑆 (hatched area) is a subset of 𝑆ℓ , while no vertex of 𝑇 (red area) has label ℓ. Any vertex of 𝑇 has all possible edges the set 𝑆. (b) Illustration of revealing three label revealing phases in Lemma 4.13 1 (yellow), 2 (red) and 3 (blue). The grey area represents a set 𝑅 with 𝑏 vertices with bounded… view at source ↗

read the original abstract

We study efficient algorithms for recovering cliques in dense random intersection graphs (RIGs). In this model, $d = n^{\Omega(1)}$ cliques of size approximately $k$ are randomly planted by choosing the vertices to participate in each clique independently with probability $\delta$. While there has been extensive work on recovering one, or multiple disjointly planted cliques in random graphs, the natural extension of this question to recovering overlapping cliques has been, surprisingly, largely unexplored. Moreover, because every vertex can be part of polynomially many cliques, this task is significantly more challenging than in case of disjointly planted cliques (as recently studied by Kothari, Vempala, Wein and Xu [COLT'23]). In this work we obtain the first efficient algorithms for recovering the community structure of RIGs both from the perspective of exact and approximate recovery. Our algorithms are further robust to noise, monotone adversaries, and a certain, optimal number of edge corruptions. They work whenever $k \gg \sqrt{n \log(n)}$. Our techniques follow the proofs-to-algorithms framework utilizing the sum-of-squares hierarchy.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives the first SOS algorithms for recovering overlapping planted cliques in random intersection graphs, with robustness to noise and adversaries.

read the letter

The key point is that this work extends planted clique recovery to the overlapping case in dense random intersection graphs, where vertices can join polynomially many cliques. Prior results handled disjoint cliques, but overlaps make the problem harder, and the authors claim the first efficient exact and approximate recovery algorithms via sum-of-squares when k is much larger than sqrt(n log n). They also add robustness to monotone adversaries and a limited number of edge corruptions, which fits the standard proofs-to-algorithms template but requires fresh analysis for the intersection model and overlap conditions. The abstract positions the result cleanly against Kothari et al., and the regime matches known SOS thresholds in related community detection settings. That part looks solid on the surface. The main soft spot is that the abstract gives no explicit SOS degree or proof outline, so it is hard to check for gaps in the certification or whether the analysis avoids post-hoc tuning. The generative model assumes independent planting with parameter delta, which is reasonable but leaves open how sensitive the guarantees are to that choice. Overall this is a targeted contribution for people working on algorithmic graph theory and planted structures. A reader already familiar with SOS for community detection would get the most out of it, especially if they care about intersection graphs or overlapping communities. The work is coherent enough on its own terms to deserve a serious referee, even if the proofs need close checking. I would send it to peer review rather than desk reject.

Referee Report

0 major / 2 minor

Summary. The manuscript develops the first efficient algorithms for recovering overlapping planted cliques in dense random intersection graphs (RIGs), where d = n^Ω(1) cliques of size ~k are planted independently with vertex-inclusion probability δ. Using the sum-of-squares hierarchy, the algorithms achieve both exact and approximate recovery of the community structure and remain robust to noise, monotone adversaries, and an optimal number of edge corruptions, succeeding whenever k ≫ √(n log n).

Significance. If the central claims hold, the work extends the proofs-to-algorithms paradigm from disjoint to overlapping cliques in RIGs, addressing a previously unexplored regime. The robustness guarantees and the threshold k ≫ √(n log n) align with known SOS thresholds in related community-recovery settings, potentially strengthening the toolkit for intersection-graph models.

minor comments (2)

[Abstract] Abstract and §1: the phrase 'a certain, optimal number of edge corruptions' is used without stating the precise corruption fraction or the corresponding theorem; adding an explicit bound (e.g., o(k^2 / n) or similar) would clarify the robustness claim.
Theorem statements (presumably §3–4): the degree of the SOS relaxation is not stated explicitly in the main recovery guarantees. Because runtime and sample complexity depend on this degree, it should appear in the theorem hypotheses.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work and for recommending minor revision. The report does not list any specific major comments to address.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation follows the standard proofs-to-algorithms paradigm by applying the sum-of-squares hierarchy to recover overlapping planted cliques in the RIG model. The paper introduces new analysis for the overlapping case, robustness to monotone adversaries and edge corruptions, and the regime k ≫ √(n log n), without reducing any target guarantee to a fitted parameter, self-defined quantity, or load-bearing self-citation. The cited prior work on disjoint cliques is by different authors and serves as contrast rather than foundational input. The central claims remain independent of the paper's own fitted values or renamings.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard random intersection graph planting model and the known properties of the sum-of-squares hierarchy; no new free parameters or invented entities are introduced in the abstract.

axioms (2)

domain assumption Cliques are planted independently by including each vertex with probability δ
This defines the generative process for the random intersection graph and is invoked throughout the model description.
domain assumption The sum-of-squares hierarchy of suitable degree can be solved in polynomial time and certifies the planted structure
This is the core algorithmic primitive used in the proofs-to-algorithms framework.

pith-pipeline@v0.9.0 · 5506 in / 1432 out tokens · 33404 ms · 2026-05-17T04:52:35.419134+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

68 extracted references · 68 canonical work pages

[1]

Community detection and stochastic block models.arXiv preprint arXiv:1703.10146, 2017

Emmanuel Abbe. Community detection and stochastic block models.arXiv preprint arXiv:1703.10146, 2017. 15

work page arXiv 2017
[2]

Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery

Emmanuel Abbe and Colin Sandon. Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In2015 IEEE 56th annual symposium on foundations of computer science, pages 670–688. IEEE, 2015. 15

work page 2015
[3]

Hölder and minkowski type inequalities for pseudo-integral.Applied Mathematics and Computation, 217(21):8630–8639, 2011

Hamzeh Agahi, Yao Ouyang, Radko Mesiar, Endre Pap, and Mirjana Štrboja. Hölder and minkowski type inequalities for pseudo-integral.Applied Mathematics and Computation, 217(21):8630–8639, 2011. 30

work page 2011
[4]

Finding a large hidden clique in a random graph.Random Structures & Algorithms, 13(3-4):457–466, 1998

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. 1, 7 71

work page 1998
[5]

Nuclearnormminimizationfortheplantedclique and biclique problems.Mathematical programming, 129(1):69–89, 2011

BrendanP.W.AmesandStephenAVavasis. Nuclearnormminimizationfortheplantedclique and biclique problems.Mathematical programming, 129(1):69–89, 2011. 1

work page 2011
[6]

Amini and Elizaveta Levina

Arash A. Amini and Elizaveta Levina. On semidefinite relaxations for the block model.The Annals of Statistics, 46(1):149 – 179, 2018.doi:10.1214/17-AOS1545. 15

work page doi:10.1214/17-aos1545 2018
[7]

Atensorspectralapproach to learning mixed membership community models

AnimashreeAnandkumar,RongGe,DanielHsu,andShamKakade. Atensorspectralapproach to learning mixed membership community models. InProceedings of the 26th Annual Conference on Learning Theory, page 867–881. PMLR, 2013. URL:https://proceedings.mlr.press/v30/ Anandkumar13.html. 5, 15, 16, 17

work page 2013
[8]

Testing thresholds and spectral properties of high-dimensional random toroidal graphs via edgeworth-style expansions

Samuel Baguley, Andreas Göbel, Marcus Pappik, and Leon Schiller. Testing thresholds and spectral properties of high-dimensional random toroidal graphs via edgeworth-style expansions. InProceedings of Thirty Eighth Conference on Learning Theory, page 200–201. PMLR,

work page
[9]

URL:https://proceedings.mlr.press/v291/baguley25a.html. 7

work page
[10]

[CGL+20] Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Sara- nurak

Ainesh Bakshi, Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar, and Pravesh K. Kothari. Outlier-Robust Clustering of Gaussians and Other Non- Spherical Mixtures . In2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 149–159, Los Alamitos, CA, USA, November 2020. IEEE Computer Society. URL: https://doi.ie...

work page doi:10.1109/focs46700.2020.00023 2020
[11]

On the fourier coefficients of high-dimensional random geometricgraphs.InProceedingsofthe56thAnnualACMSymposiumonTheoryofComputing,STOC 2024, page 549–560, New York, NY, USA, 2024

Kiril Bangachev and Guy Bresler. On the fourier coefficients of high-dimensional random geometricgraphs.InProceedingsofthe56thAnnualACMSymposiumonTheoryofComputing,STOC 2024, page 549–560, New York, NY, USA, 2024. Association for Computing Machinery. URL: https://dl.acm.org/doi/10.1145/3618260.3649676,doi:10.1145/3618260.3649676. 7

work page doi:10.1145/3618260.3649676 2024
[12]

Kothari, Ankur Moitra, and Aaron Potechin

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, January 2019.doi:10.1137/17M1138236. 1, 14

work page doi:10.1137/17m1138236 2019
[13]

2019.09.018,doi:10.1016/J.TCS.2019.09.018

Michael Behrisch and Anusch Taraz. Efficiently covering complex networks with cliques of similar vertices.Theoretical Computer Science, 355(1):37–47, April 2006.doi:10.1016/j.tcs. 2005.12.005. 2, 3, 81

work page doi:10.1016/j.tcs 2006
[14]

Coloring random intersection graphs and complex networks.SIAM Journal on Discrete Mathematics, 23(1):288–299, 2009

Michael Behrisch, Anusch Taraz, and Michael Ueckerdt. Coloring random intersection graphs and complex networks.SIAM Journal on Discrete Mathematics, 23(1):288–299, 2009. 2, 3

work page 2009
[15]

Semirandom planted clique and the restricted isometry property

Jarosław Błasiok, Rares-Darius Buhai, Pravesh K Kothari, and David Steurer. Semirandom planted clique and the restricted isometry property. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 959–969. IEEE, 2024. 1, 2

work page 2024
[16]

Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs

Charles Bordenave, Marc Lelarge, and Laurent Massoulié. Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs. In2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1347–1357. IEEE, 2015. 15

work page 2015
[17]

Reducibilityandstatistical-computationalgapsfromsecret leakage

MatthewBrennanandGuyBresler. Reducibilityandstatistical-computationalgapsfromsecret leakage. InConference on Learning Theory, pages 648–847. PMLR, 2020. 1 72

work page 2020
[18]

Reducibility and computational lower bounds for problems with planted sparse structure

Matthew Brennan, Guy Bresler, and Wasim Huleihel. Reducibility and computational lower bounds for problems with planted sparse structure. InConference On Learning Theory, pages 48–166. PMLR, 2018. 1

work page 2018
[19]

Phase transitions for detecting latent geometry in random graphs.Probability Theory and Related Fields, 178(3):1215–1289, December 2020.doi:10.1007/s00440-020-00998-3

Matthew Brennan, Guy Bresler, and Dheeraj Nagaraj. Phase transitions for detecting latent geometry in random graphs.Probability Theory and Related Fields, 178(3):1215–1289, December 2020.doi:10.1007/s00440-020-00998-3. 5

work page doi:10.1007/s00440-020-00998-3 2020
[20]

Algorithmic decorrelation and planted clique in dependent random graphs: the case of extra triangles

Guy Bresler, Chenghao Guo, and Yury Polyanskiy. Algorithmic decorrelation and planted clique in dependent random graphs: the case of extra triangles. In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 2149–2158. IEEE, 2023. 1

work page 2023
[21]

Thresholds for reconstruction of random hypergraphsfromgraphprojections

Guy Bresler, Chenghao Guo, and Yury Polyanskiy. Thresholds for reconstruction of random hypergraphsfromgraphprojections. InTheThirtySeventhAnnualConferenceonLearningTheory, pages 632–647. PMLR, 2024. 5, 6

work page 2024
[22]

Partial and exact recovery of a random hypergraph from its graph projection.arXiv preprint arXiv:2502.14988, 2025

Guy Bresler, Chenghao Guo, Yury Polyanskiy, and Andrew Yao. Partial and exact recovery of a random hypergraph from its graph projection.arXiv preprint arXiv:2502.14988, 2025. 3, 5, 6

work page arXiv 2025
[23]

Kothari, and David Steurer

Rares-Darius Buhai, Pravesh K. Kothari, and David Steurer. Algorithms approaching the thresholdforsemi-randomplantedclique. InSTOC’23,2023. doi:10.1145/3564246.3585184. 1, 2, 8, 9, 19, 31, 32, 33, 45, 47

work page doi:10.1145/3564246.3585184 2023
[24]

Improved robust estimation for erdős-rényi graphs: The sparse regime and optimal breakdown point

Hongjie Chen, Jingqiu Ding, Yiding Hua, and Stefan Tiegel. Improved robust estimation for erdős-rényi graphs: The sparse regime and optimal breakdown point. (arXiv:2503.03923), March2025. arXiv:2503.03923[cs]. URL:http://arxiv.org/abs/2503.03923, doi:10.48550/ arXiv.2503.03923. 7

work page arXiv
[25]

Yudong Chen and Jiaming Xu. Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices.Journal of Machine Learning Research, 17(27):1–57, 2016. 1

work page 2016
[26]

Spirakis

Filippos Christodoulou, Sotiris Nikoletseas, Christoforos Raptopoulos, and Paul G. Spirakis. A spectral algorithm for finding maximum cliques in dense random intersection graphs. In Leszek Gąsieniec, editor,SOFSEM 2023: Theory and Practice of Computer Science, page 18–32, Cham, 2023. Springer International Publishing.doi:10.1007/978-3-031-23101-8_2. 2, 3

work page doi:10.1007/978-3-031-23101-8_2 2023
[27]

Graph partitioning via adaptive spectral techniques.Combinatorics, Probability and Computing, 19(2):227–284, 2010

Amin Coja-Oghlan. Graph partitioning via adaptive spectral techniques.Combinatorics, Probability and Computing, 19(2):227–284, 2010. 15

work page 2010
[28]

Finding hidden cliques in linear time with high probability.Combinatorics, Probability and Computing, 23(1):29–49, 2014

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. 1

work page 2014
[29]

Finding hidden cliques of size n/e in nearly linear time.Foundations of Computational Mathematics, 15(4):1069–1128, 2015

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. 1

work page 2015
[30]

Improved sum-of-squares lower bounds for hidden cliqueandhiddensubmatrixproblems

Yash Deshpande and Andrea Montanari. Improved sum-of-squares lower bounds for hidden cliqueandhiddensubmatrixproblems. InConferenceonLearningTheory,pages523–562.PMLR,

work page
[31]

[JS21] Wenyu Jin and Xiaorui Sun

JingqiuDing,TommasoD’Orsi,RajaiNasser,andDavidSteurer. Robustrecoveryforstochastic block models. page 387–394. IEEE Computer Society, February 2022. URL:https://www. computer.org/csdl/proceedings-article/focs/2022/205500a387/1BtfG9j304g, doi:10. 1109/FOCS52979.2021.00046. 17

work page arXiv 2022
[32]

How to hide a clique?Theory of Computing Systems, 68(4):773–813, August 2024.doi:10.1007/s00224-024-10167-x

Uriel Feige and Vadim Grinberg. How to hide a clique?Theory of Computing Systems, 68(4):773–813, August 2024.doi:10.1007/s00224-024-10167-x. 2, 80

work page doi:10.1007/s00224-024-10167-x 2024
[33]

Heuristics for semirandom graph problems.Journal of Computer and System Sciences, 63(4):639–671, 2001

Uriel Feige and Joe Kilian. Heuristics for semirandom graph problems.Journal of Computer and System Sciences, 63(4):639–671, 2001. 3

work page 2001
[34]

Finding and certifying a large hidden clique in a semirandom graph.Random Structures and Algorithms, 16(2):195–208, 2000

Uriel Feige and Robert Krauthgamer. Finding and certifying a large hidden clique in a semirandom graph.Random Structures and Algorithms, 16(2):195–208, 2000. 1

work page 2000
[35]

Finding hidden cliques in linear time.Discrete Mathematics & Theoretical Computer Science, (Proceedings), 2010

Uriel Feige and Dorit Ron. Finding hidden cliques in linear time.Discrete Mathematics & Theoretical Computer Science, (Proceedings), 2010. 1

work page 2010
[36]

Statistical algorithms and a lower bound for detecting planted cliques.Journal of the ACM (JACM), 64(2):1–37, 2017

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. 1

work page 2017
[37]

Semialgebraic proofs and efficient algorithm design.Foundations and Trends®in Theoretical Computer Science, 14(1–2):1–221, December 2019.doi:10.1561/0400000086

Noah Fleming, Pravesh Kothari, and Toniann Pitassi. Semialgebraic proofs and efficient algorithm design.Foundations and Trends®in Theoretical Computer Science, 14(1–2):1–221, December 2019.doi:10.1561/0400000086. 6, 29

work page doi:10.1561/0400000086 2019
[38]

Community detection in sparse networks via grothendieck’s inequality.Probability Theory and Related Fields, 165(3):1025–1049, 2016

Olivier Guédon and Roman Vershynin. Community detection in sparse networks via grothendieck’s inequality.Probability Theory and Related Fields, 165(3):1025–1049, 2016. 15

work page 2016
[39]

Computational lower bounds for community detection on random graphs

Bruce Hajek, Yihong Wu, and Jiaming Xu. Computational lower bounds for community detection on random graphs. InConference on Learning Theory, pages 899–928. PMLR, 2015. 1

work page 2015
[40]

Clique is hard to approximate within n1tildeeps.Acta Mathematica, 182(1):105–142, January 1999.doi:10.1007/BF02392825

Johan Høastad. Clique is hard to approximate within n1tildeeps.Acta Mathematica, 182(1):105–142, January 1999.doi:10.1007/BF02392825. 1

work page doi:10.1007/bf02392825 1999
[41]

On the integrality gap of degree-4 sum of squares for planted clique.ACM Transactions on Algorithms (TALG), 14(3):1–31, 2018

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. 1

work page 2018
[42]

Hopkins and David Steurer

Samuel B. Hopkins and David Steurer. Efficient bayesian estimation from few sam- ples: Community detection and related problems. page 379–390. IEEE Computer Society, October 2017. URL:https://www.computer.org/csdl/proceedings-article/focs/2017/ 3464a379/12OmNxWLTst,doi:10.1109/FOCS.2017.42. 5, 15, 16, 17

work page doi:10.1109/focs.2017.42 2017
[43]

Large cliques elude the metropolis process.Random Structures & Algorithms, 3(4):347–359, 1992

Mark Jerrum. Large cliques elude the metropolis process.Random Structures & Algorithms, 3(4):347–359, 1992. 1

work page 1992
[44]

On the computational complexity of combinatorial problems.Networks, 5(1):45–68, 1975

Richard M Karp. On the computational complexity of combinatorial problems.Networks, 5(1):45–68, 1975. 1 74

work page 1975
[45]

Springer, 2008

Achim Klenke.Probability theory: a comprehensive course. Springer, 2008. 76

work page 2008
[46]

Is planted coloring easier than planted clique? InThe Thirty Sixth Annual Conference on Learning Theory, pages 5343–5372

Pravesh Kothari, Santosh S Vempala, Alexander S Wein, and Jeff Xu. Is planted coloring easier than planted clique? InThe Thirty Sixth Annual Conference on Learning Theory, pages 5343–5372. PMLR, 2023. 1, 2, 5, 78

work page 2023
[47]

Isplantedcoloringeasier thanplantedclique? InProceedingsofThirtySixthConferenceonLearningTheory,page5343–5372

PraveshKothari,SantoshS.Vempala,AlexanderS.Wein,andJeffXu. Isplantedcoloringeasier thanplantedclique? InProceedingsofThirtySixthConferenceonLearningTheory,page5343–5372. PMLR, 2023. URL:https://proceedings.mlr.press/v195/kothari23a.html. 14

work page 2023
[48]

Spectral redemption in clustering sparse networks.Proceedings of the National Academy of Sciences, 110(52):20935–20940, 2013

FlorentKrzakala,CristopherMoore,ElchananMossel,JoeNeeman,AllanSly,LenkaZdeborová, and Pan Zhang. Spectral redemption in clustering sparse networks.Proceedings of the National Academy of Sciences, 110(52):20935–20940, 2013. 15

work page 2013
[49]

Expected complexity of graph partitioning problems.Discrete Applied Mathe- matics, 57(2-3):193–212, 1995

Luděk Kučera. Expected complexity of graph partitioning problems.Discrete Applied Mathe- matics, 57(2-3):193–212, 1995. 1

work page 1995
[50]

New positive semidefinite relaxations for nonconvex quadratic programs

Jean B Lasserre. New positive semidefinite relaxations for nonconvex quadratic programs. In Advances in Convex Analysis and Global Optimization: Honoring the Memory of C. Caratheodory (1873–1950), pages 319–331. Springer, 2001. 30, 51

work page 1950
[51]

Can M. Le. Estimating community structure in networks by spectral methods. 2016. URL: https://hdl.handle.net/2027.42/133258. 7

work page 2016
[52]

The fundamental limits of recovering planted subgraphs.arXiv preprint arXiv:2503.15723, 2025

Daniel Lee, Francisco Pernice, Amit Rajaraman, and Ilias Zadik. The fundamental limits of recovering planted subgraphs.arXiv preprint arXiv:2503.15723, 2025. 1

work page arXiv 2025
[53]

Spectral clustering in the gaussian mixture block model

Shuangping Li and Tselil Schramm. Spectral clustering in the gaussian mixture block model. (arXiv:2305.00979), April 2024. arXiv:2305.00979 [stat]. URL:http://arxiv.org/abs/2305. 00979,doi:10.48550/arXiv.2305.00979. 7

work page doi:10.48550/arxiv.2305.00979 2024
[54]

Perfect recovery for random geometric graph matching with shallow graph neural networks

Suqi Liu and Morgane Austern. Perfect recovery for random geometric graph matching with shallow graph neural networks. InProceedings of The 28th International Conference on Artificial Intelligence and Statistics, page 910–918. PMLR, April 2025. URL:https://proceedings.mlr. press/v258/liu25c.html. 5

work page 2025
[55]

Xueyu Mao, Purnamrita Sarkar, and Deepayan Chakrabarti. Estimating mixed mem- berships with sharp eigenvector deviations.Journal of the American Statistical Associa- tion, 116(536):1928–1940, 2021.arXiv:https://doi.org/10.1080/01621459.2020.1751645, doi:10.1080/01621459.2020.1751645. 15

work page doi:10.1080/01621459.2020.1751645 1928
[56]

Spectral partitioning of random graphs

Frank McSherry. Spectral partitioning of random graphs. InProceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 529–537. IEEE, 2001. 1

work page 2001
[57]

Sum-of-squares lower bounds for planted clique

Raghu Meka, Aaron Potechin, and Avi Wigderson. Sum-of-squares lower bounds for planted clique. InProceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 87–96, 2015. 1 75

work page 2015
[58]

Sidhanth Mohanty, Prasad Raghavendra, and David X. Wu. Robust recovery for stochastic block models, simplified and generalized. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, page 367–374, New York, NY, USA, 2024. Association forComputingMachinery. URL: https://dl.acm.org/doi/10.1145/3618260.3649761, doi: 10.1145/3618260...

work page doi:10.1145/3618260.3649761 2024
[59]

AnkurMoitra,WilliamPerry,andAlexanderS.Wein. Howrobustarereconstructionthresholds for community detection? InProceedings of the forty-eighth annual ACM symposium on Theory of Computing, STOC ’16, page 828–841, New York, NY, USA, 2016. Association for Computing Machinery.doi:10.1145/2897518.2897573. 2, 71

work page doi:10.1145/2897518.2897573 2016
[60]

Semidefinite programs on sparse random graphs and their application to community detection

Andrea Montanari and Subhabrata Sen. Semidefinite programs on sparse random graphs and their application to community detection. InProceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 814–827, 2016. 15

work page 2016
[61]

Reconstruction and estimation in the planted partition model.Probability Theory and Related Fields, 162(3):431–461, 2015

Elchanan Mossel, Joe Neeman, and Allan Sly. Reconstruction and estimation in the planted partition model.Probability Theory and Related Fields, 162(3):431–461, 2015. 15

work page 2015
[62]

Squared functional systems and optimization problems

Yurii Nesterov. Squared functional systems and optimization problems. InHigh performance optimization, pages 405–440. Springer, 2000. 30, 51

work page 2000
[63]

Nikoletseas, Christoforos L

Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, and Paul G. Spirakis. Maximum cliques in graphs with small intersection number and random intersection graphs. InMFCS’12, 2012. doi:10.1007/978-3-642-32589-2\_63. 4, 6, 7, 14, 38

work page doi:10.1007/978-3-642-32589-2 2012
[64]

Maximum cliques in graphs with small intersection number and random intersection graphs.Computer Science Review, 39:100353, 2021

Sotiris E Nikoletseas, Christoforos L Raptopoulos, and Paul G Spirakis. Maximum cliques in graphs with small intersection number and random intersection graphs.Computer Science Review, 39:100353, 2021. 2, 3, 4, 7

work page 2021
[65]

California Institute of Technology, 2000

Pablo A Parrilo.Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. California Institute of Technology, 2000. 30, 51

work page 2000
[66]

Computational barriers to estimation from low-degree polynomials.The Annals of Statistics, 50(3):1833–1858, 2022

Tselil Schramm and Alexander S Wein. Computational barriers to estimation from low-degree polynomials.The Annals of Statistics, 50(3):1833–1858, 2022. 1

work page 2022
[67]

Optimal cluster recovery in the labeled stochastic block model.Advances in Neural Information Processing Systems, 29, 2016

Se-Young Yun and Alexandre Proutiere. Optimal cluster recovery in the labeled stochastic block model.Advances in Neural Information Processing Systems, 29, 2016. 15

work page 2016
[68]

planting

David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. InProceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 681–690, 2006. 1 A Lower bound on the spectral gap of RIGs In this section we prove the lower-bound on the spectral norm of the centered adjacency matrix of a random i...

work page 2006