Imagen de Portada

Spectral Clustering in Birthday Paradox Time

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Kapralov, Michael, Kochetkova, Ekaterina, Wrzos-Kaminska, Weronika
Formato:	Preprint
Publicado:	2026
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Spectral Clustering with Side Information
por: Fichtenberger, Hendrik, et al.
Publicado: (2025)

Recovering Communities in Structured Random Graphs
por: Kapralov, Michael, et al.
Publicado: (2026)

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

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

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

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

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

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

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

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

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

Streaming Algorithms for Connectivity Augmentation
por: Jin, Ce, et al.
Publicado: (2024)

The Strong Birthday Problem Revisited
por: Tripathy, Chijul B.
Publicado: (2025)

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

Sublinear Spectral Clustering Oracle with Little Memory
por: Shen, Ranran, et al.
Publicado: (2026)

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

Coreset Spectral Clustering
por: Jourdan, Ben, et al.
Publicado: (2025)

Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player
por: Agassy, Daniel, et al.
Publicado: (2022)

Solving the Correlation Cluster LP in Sublinear Time
por: Cao, Nairen, et al.
Publicado: (2025)

Local Search for Clustering in Almost-linear Time
por: Jiang, Shaofeng H. -C., et al.
Publicado: (2025)

Deterministic $k$-Median Clustering in Near-Optimal Time
por: Costa, Martín, et al.
Publicado: (2025)

Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering
por: Nezhad, Sina Bagheri, et al.
Publicado: (2025)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
por: Dai, Han, et al.
Publicado: (2025)

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
por: Driemel, Anne, et al.
Publicado: (2026)

Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse
por: Bhattacharya, Sayan, et al.
Publicado: (2024)

A Polynomial-time Algorithm for Detecting the Possibility of Braess Paradox in Directed Graphs
por: Cenciarelli, Pietro, et al.
Publicado: (2016)

Dynamic Spectral Clustering with Provable Approximation Guarantee
por: Laenen, Steinar, et al.
Publicado: (2024)

Understanding the Cluster LP for Correlation Clustering
por: Cao, Nairen, et al.
Publicado: (2024)

SpEx: A Spectral Approach to Explainable Clustering
por: Argov, Tal, et al.
Publicado: (2025)

Beyond Spectral Clustering: Probabilistic Cuts for Differentiable Graph Partitioning
por: Ghriss, Ayoub
Publicado: (2025)

Combinatorial Correlation Clustering
por: Cohen-Addad, Vincent, et al.
Publicado: (2024)

Coresets for Kernel Clustering
por: Jiang, Shaofeng H. -C., et al.
Publicado: (2021)

Clustering in Varying Metrics
por: Chakrabarty, Deeparnab, et al.
Publicado: (2025)

Competitively Consistent Clustering
por: Buchbinder, Niv, et al.
Publicado: (2025)

A Theory of Spectral CSP Sparsification
por: Khanna, Sanjeev, et al.
Publicado: (2025)

Fully Dynamic Spectral Sparsification of Hypergraphs
por: Goranci, Gramoz, et al.
Publicado: (2025)

1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP
por: Lee, Dahoon, et al.
Publicado: (2025)

Distributed Algorithms for Euclidean Clustering
por: Cohen-Addad, Vincent, et al.
Publicado: (2026)

Fully Dynamic Spectral Sparsification for Directed Hypergraphs
por: Forster, Sebastian, et al.
Publicado: (2025)

On Parallel $k$-Center Clustering
por: Coy, Sam, et al.
Publicado: (2023)