Cover Image

On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bhaskara, Aditya, Jha, Agastya Vibhuti, Kapralov, Michael, Manoj, Naren Sarayu, Mazzali, Davide, Wrzos-Kaminska, Weronika
Format:	Preprint
Published:	2024
Subjects:	Machine Learning Data Structures and Algorithms Social and Information Networks
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)

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

Recovering Communities in Structured Random Graphs
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)

The Change-of-Measure Method, Block Lewis Weights, and Approximating Matrix Block Norms
by: Manoj, Naren Sarayu, et al.
Published: (2023)

Near-Optimal Constructive Bounds for $\ell_2$ Prefix Discrepancy and Steinitz Problems via Affine Spectral Independence
by: Dutta, Kunal, et al.
Published: (2026)

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

Spectral Refutations of Semirandom $k$-LIN over Larger Fields
by: Kocurek, Nicholas, et al.
Published: (2025)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
by: Anand, Aditya, et al.
Published: (2025)

Semirandom Planted Clique and the Restricted Isometry Property
by: Błasiok, Jarosław, et al.
Published: (2024)

Improved Certificates for Independence Number in Semirandom Hypergraphs
by: Kothari, Pravesh, et al.
Published: (2026)

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

Semidefinite Programming for the Asymmetric Stochastic Block Model
by: Gaudio, Julia, et al.
Published: (2025)

New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries
by: Bhaskara, Aditya, et al.
Published: (2024)

Optimizing Probabilistic Propagation in Graphs by Adding Edges
by: Bhaskara, Aditya, et al.
Published: (2024)

Semirandom Planted Clique via 1-norm Isometry Property
by: Guruswami, Venkatesan, et al.
Published: (2025)

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

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

Online Distributed Queue Length Estimation
by: Bhaskara, Aditya, et al.
Published: (2025)

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

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

Protecting participants or population? Comparison of k-anonymous Origin-Destination matrices
by: Armenante, Pietro, et al.
Published: (2025)

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

Robust Parameter Fitting to Realistic Network Models via Iterative Stochastic Approximation
by: Bläsius, Thomas, et al.
Published: (2024)

Matching Algorithms in the Sparse Stochastic Block Model
by: Brandenberger, Anna, et al.
Published: (2024)

Streaming Stochastic Submodular Maximization with On-Demand User Requests
by: Wang, Honglian, et al.
Published: (2026)

Improved Approximation Algorithms for Index Coding
by: Chawin, Dror, et al.
Published: (2024)

Investigations on Algorithm Selection for Interval-Based Coding Methods
by: Strutz, Tilo, et al.
Published: (2024)

On the Feasible Region of Efficient Algorithms for Attributed Graph Alignment
by: Wang, Ziao, et al.
Published: (2022)

Bounds and Algorithms for Alphabetic Codes and Binary Search Trees
by: Bruno, Roberto, et al.
Published: (2024)

Efficient Algorithms for Attributed Graph Alignment with Vanishing Edge Correlation
by: Wang, Ziao, et al.
Published: (2023)

Algorithmic Improvements to List Decoding of Folded Reed-Solomon Codes
by: Ashvinkumar, Vikrant, et al.
Published: (2025)

Robust Gray Codes Approaching the Optimal Rate
by: Con, Roni, et al.
Published: (2024)

Guessing Efficiently for Constrained Subspace Approximation
by: Bhaskara, Aditya, et al.
Published: (2025)

An Optimal Algorithm for Stochastic Vertex Cover
by: Brand, Jan van den, et al.
Published: (2026)

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

Near-optimal Algorithms for Stochastic Online Bin Packing
by: Ayyadevara, Nikhil, et al.
Published: (2022)

Improved 2-Approximate Shortest Paths for close vertex pairs
by: Gupta, Manoj
Published: (2025)

Necessity of Block Designs for Optimal Locally Private Distribution Estimation
by: Gentle, Abigail
Published: (2025)