Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2511.20376 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914462328422400 |
|---|---|
| author | Göbel, Andreas Ruff, Janosch Schiller, Leon |
| author_facet | Göbel, Andreas Ruff, Janosch Schiller, Leon |
| contents | We study efficient algorithms for recovering cliques in dense random intersection graphs (RIGs). In this model, $d = n^{Ω(1)}$ cliques of size approximately $k$ are randomly planted by choosing the vertices to participate in each clique independently with probability $δ$. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_20376 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares Göbel, Andreas Ruff, Janosch Schiller, Leon Data Structures and Algorithms 68Q87 We study efficient algorithms for recovering cliques in dense random intersection graphs (RIGs). In this model, $d = n^{Ω(1)}$ cliques of size approximately $k$ are randomly planted by choosing the vertices to participate in each clique independently with probability $δ$. 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. |
| title | Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares |
| topic | Data Structures and Algorithms 68Q87 |
| url | https://arxiv.org/abs/2511.20376 |