Cover Image

Sublinear Spectral Clustering Oracle with Little Memory

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Shen, Ranran, Zhu, Xiaoyi, Peng, Pan, Huang, Zengfeng
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

A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time
by: Shen, Ranran, et al.
Published: (2023)

Space Complexity of Euclidean Clustering
by: Zhu, Xiaoyi, et al.
Published: (2024)

Sublinear Algorithms for Estimating Single-Linkage Clustering Costs
by: Peng, Pan, et al.
Published: (2025)

Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models
by: Huang, Zengfeng, et al.
Published: (2025)

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

Improved Algorithms for Clustering with Noisy Distance Oracles
by: Pradhan, Pinki, et al.
Published: (2026)

Sublinear Edge Fault Tolerant Spanners for Hypergraphs
by: He, Jialin, et al.
Published: (2025)

Dynamic Correlation Clustering in Sublinear Update Time
by: Cohen-Addad, Vincent, et al.
Published: (2024)

Relative Error Fair Clustering in the Weak-Strong Oracle Model
by: Braverman, Vladimir, et al.
Published: (2025)

Computing String Covers in Sublinear Time
by: Radoszewski, Jakub, et al.
Published: (2024)

On Solving Linear Systems in Sublinear Time
by: Andoni, Alexandr, et al.
Published: (2018)

Almost-Optimal Sublinear Additive Spanners
by: Tan, Zihan, et al.
Published: (2023)

Simple and Optimal Sublinear Algorithms for Mean Estimation
by: Bertolotti, Beatrice, et al.
Published: (2024)

Counting Distinct Square Substrings in Sublinear Time
by: Charalampopoulos, Panagiotis, et al.
Published: (2025)

Sublinear Algorithms for TSP via Path Covers
by: Behnezhad, Soheil, et al.
Published: (2023)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
by: Goranci, Gramoz, et al.
Published: (2023)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
by: Bernstein, Aaron, et al.
Published: (2025)

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring
by: Ferber, Asaf, et al.
Published: (2025)

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

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
by: Dai, Jiangqi, et al.
Published: (2025)

Lempel-Ziv (LZ77) Factorization in Sublinear Time
by: Kempa, Dominik, et al.
Published: (2024)

Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time
by: Eden, Talya, et al.
Published: (2025)

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

Hamming Distance Oracle
by: Boneh, Itai, et al.
Published: (2024)

Query-Efficient Correlation Clustering with Noisy Oracle
by: Kuroki, Yuko, et al.
Published: (2024)

Minimizing Makespan in Sublinear Time via Weighted Random Sampling
by: Fu, Bin, et al.
Published: (2026)

Sublinear Metric Steiner Forest via Maximal Independent Set
by: Mahabadi, Sepideh, et al.
Published: (2025)

Improved Sublinear-time Moment Estimation using Weighted Sampling
by: Bhattacharya, Anup, et al.
Published: (2025)

On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time
by: Kwok, Tsz Chiu, et al.
Published: (2025)

Gapped String Indexing in Subquadratic Space and Sublinear Query Time
by: Bille, Philip, et al.
Published: (2022)

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

Approximate Butterfly Counting in Sublinear Time
by: Luo, Chi, et al.
Published: (2026)

Hyper-distance Oracles in Hypergraphs
by: Preti, Giulia, et al.
Published: (2023)

Distributed Distance Sensitivity Oracles
by: Manoharan, Vignesh, et al.
Published: (2024)

Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries
by: Chen, Xi, et al.
Published: (2024)

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
by: Mahabadi, Sepideh, et al.
Published: (2024)

Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
by: Goranci, Gramoz, et al.
Published: (2025)

Two Linear Passes Are Necessary for Sum-Exclude-Self Under Sublinear Space
by: Au, Andrew
Published: (2026)

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

Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries
by: Bishnu, Arijit, et al.
Published: (2025)