Buchumschlag

Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Kapralov, Michael, Kumar, Akash, Lattanzi, Silvio, Mousavifar, Aida, Wrzos-Kaminska, Weronika
Format:	Preprint
Veröffentlicht:	2022
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Recovering Communities in Structured Random Graphs
von: Kapralov, Michael, et al.
Veröffentlicht: (2026)

Spectral Clustering in Birthday Paradox Time
von: Kapralov, Michael, et al.
Veröffentlicht: (2026)

Spectral Clustering with Side Information
von: Fichtenberger, Hendrik, et al.
Veröffentlicht: (2025)

Weighted Matching in the Random-Order Streaming and Robust Communication Models
von: Hashemi, Diba, et al.
Veröffentlicht: (2024)

Sublinear Time Low-Rank Approximation of Hankel Matrices
von: Kapralov, Michael, et al.
Veröffentlicht: (2025)

On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models
von: Bhaskara, Aditya, et al.
Veröffentlicht: (2024)

Dynamic Correlation Clustering in Sublinear Update Time
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2024)

A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2024)

Approximate Butterfly Counting in Sublinear Time
von: Luo, Chi, et al.
Veröffentlicht: (2026)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
von: Dai, Jiangqi, et al.
Veröffentlicht: (2025)

Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time
von: Eden, Talya, et al.
Veröffentlicht: (2025)

Minimizing Makespan in Sublinear Time via Weighted Random Sampling
von: Fu, Bin, et al.
Veröffentlicht: (2026)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
von: Jiang, Shunhua, et al.
Veröffentlicht: (2025)

A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time
von: Mahabadi, Sepideh, et al.
Veröffentlicht: (2025)

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
von: Shah, Vihan
Veröffentlicht: (2026)

Sublinear Algorithms for Estimating Single-Linkage Clustering Costs
von: Peng, Pan, et al.
Veröffentlicht: (2025)

Almost Tight Bounds for Differentially Private Densest Subgraph
von: Dinitz, Michael, et al.
Veröffentlicht: (2023)

Sublinear Time Low-Rank Approximation of Toeplitz Matrices
von: Musco, Cameron, et al.
Veröffentlicht: (2024)

Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

On the adversarial robustness of Locality-Sensitive Hashing in Hamming space
von: Kapralov, Michael, et al.
Veröffentlicht: (2024)

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
von: Charikar, Moses, et al.
Veröffentlicht: (2024)

Sublinear Random Access Generators for Preferential Attachment Graphs
von: Even, Guy, et al.
Veröffentlicht: (2016)

Computing String Covers in Sublinear Time
von: Radoszewski, Jakub, et al.
Veröffentlicht: (2024)

On Solving Linear Systems in Sublinear Time
von: Andoni, Alexandr, et al.
Veröffentlicht: (2018)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
von: Moroie, Gregory
Veröffentlicht: (2025)

Approximation Algorithms for Digraph Width Parameters
von: Kintali, Shiva, et al.
Veröffentlicht: (2011)

Solving the Correlation Cluster LP in Sublinear Time
von: Cao, Nairen, et al.
Veröffentlicht: (2025)

Counting Distinct Square Substrings in Sublinear Time
von: Charalampopoulos, Panagiotis, et al.
Veröffentlicht: (2025)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
von: Goranci, Gramoz, et al.
Veröffentlicht: (2023)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)

Lempel-Ziv (LZ77) Factorization in Sublinear Time
von: Kempa, Dominik, et al.
Veröffentlicht: (2024)

Provable Quantization with Randomized Hadamard Transform
von: Feng, Ying, et al.
Veröffentlicht: (2026)

On the Streaming Complexity of Expander Decomposition
von: Chen, Yu, et al.
Veröffentlicht: (2024)

Streaming Algorithms for Connectivity Augmentation
von: Jin, Ce, et al.
Veröffentlicht: (2024)

Sublinear Time Quantum Algorithm for Attention Approximation
von: Song, Zhao, et al.
Veröffentlicht: (2026)

Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries
von: Bishnu, Arijit, et al.
Veröffentlicht: (2025)

Gapped String Indexing in Subquadratic Space and Sublinear Query Time
von: Bille, Philip, et al.
Veröffentlicht: (2022)

On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time
von: Kwok, Tsz Chiu, et al.
Veröffentlicht: (2025)

Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs
von: Kumar, Akash, et al.
Veröffentlicht: (2026)