Cover Image

Recovering Communities in Structured Random Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kapralov, Michael, Trevisan, Luca, Wrzos-Kaminska, Weronika
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Spectral Clustering in Birthday Paradox Time
by: Kapralov, Michael, et al.
Published: (2026)

Weighted Matching in the Random-Order Streaming and Robust Communication Models
by: Hashemi, Diba, et al.
Published: (2024)

Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds
by: Kapralov, Michael, et al.
Published: (2022)

Spectral Clustering with Side Information
by: Fichtenberger, Hendrik, et al.
Published: (2025)

On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models
by: Bhaskara, Aditya, et al.
Published: (2024)

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
by: Charikar, Moses, et al.
Published: (2024)

Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
by: Jiang, Shunhua, et al.
Published: (2025)

On the adversarial robustness of Locality-Sensitive Hashing in Hamming space
by: Kapralov, Michael, et al.
Published: (2024)

Provable Quantization with Randomized Hadamard Transform
by: Feng, Ying, et al.
Published: (2026)

On the Streaming Complexity of Expander Decomposition
by: Chen, Yu, et al.
Published: (2024)

Streaming Algorithms for Connectivity Augmentation
by: Jin, Ce, et al.
Published: (2024)

Sublinear Time Low-Rank Approximation of Hankel Matrices
by: Kapralov, Michael, et al.
Published: (2025)

Sorting and Selection in Rounds with Adversarial Comparisons
by: Trevisan, Chris
Published: (2023)

Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions
by: Indyk, Piotr, et al.
Published: (2025)

Faster Estimation of the Average Degree of a Graph Using Random Edges and Structural Queries
by: Beretta, Lorenzo, et al.
Published: (2025)

Diameter Computation on (Random) Geometric Graphs
by: Bläsius, Thomas, et al.
Published: (2026)

Online Matching in Geometric Random Graphs
by: Sentenac, Flore, et al.
Published: (2023)

Explicit Combinatoric Structures of Palindromes and Chromatic Number of Restriction Graphs
by: Amir, Amihood, et al.
Published: (2024)

Estimating Random-Walk Probabilities in Directed Graphs
by: Bertram, Christian, et al.
Published: (2025)

Sublinear Random Access Generators for Preferential Attachment Graphs
by: Even, Guy, et al.
Published: (2016)

Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring
by: Baguley, Samuel, et al.
Published: (2024)

Proceedings of the 13th edition of the conference on Random Generation of Combinatorial Structures. Polyominoes and Tilings
by: Brlek, Srečko, et al.
Published: (2024)

Random Generation of Git Graphs
by: Courtiel, Julien, et al.
Published: (2024)

Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs
by: Kumar, Akash, et al.
Published: (2026)

Multi-View Structural Graph Summaries
by: Frank, Jonatan, et al.
Published: (2024)

Contiguous Graph Partitioning For Optimal Total Or Bottleneck Communication
by: Ahrens, Willow
Published: (2020)

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
by: Kothari, Pravesh, et al.
Published: (2024)

Distance Reconstruction of Sparse Random Graphs
by: Bastide, Paul
Published: (2024)

Hitting Geodesic Intervals in Structurally Restricted Graphs
by: Gima, Tatsuya, et al.
Published: (2025)

Creating Robust and Fair Graph Structures for Connectivity and Clustering
by: Chatterjee, Kushagra
Published: (2026)

Succinct Data Structure for Graphs with $d$-Dimensional $t$-Representation
by: Balakrishnan, Girish, et al.
Published: (2023)

New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification
by: Ghosh, Prantar, et al.
Published: (2024)

Real-World Graph Analysis: Techniques for Static, Dynamic, and Temporal Communities
by: Rucci, Davide
Published: (2024)

Streaming Attention Approximation via Discrepancy Theory
by: Kochetkova, Ekaterina, et al.
Published: (2025)

A Framework for Building Data Structures from Communication Protocols
by: Andoni, Alexandr, et al.
Published: (2025)

Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage
by: Balakrishnan, Girish, et al.
Published: (2024)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
by: Bodwin, Greg, et al.
Published: (2024)

Randomized Communication and Implicit Graph Representations
by: Harms, Nathaniel, et al.
Published: (2021)

Rapid Mixing on Random Regular Graphs beyond Uniqueness
by: Chen, Xiaoyu, et al.
Published: (2025)

Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing
by: Eppstein, David, et al.
Published: (2025)