Cover Image

Improved Sublinear-time Moment Estimation using Weighted Sampling

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bhattacharya, Anup, Pradhan, Pinki
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Distribution Testing Meets Sum Estimation
by: Pradhan, Pinki, et al.
Published: (2025)

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

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

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

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

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

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

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

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

Sublinear Time Algorithm for Online Weighted Bipartite Matching
by: Hu, Hang, et al.
Published: (2022)

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)

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

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

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

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)

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

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
by: Shah, Vihan
Published: (2026)

Differential privacy and Sublinear time are incompatible sometimes
by: Blocki, Jeremiah, et al.
Published: (2024)

Perfect Sampling in Turnstile Streams Beyond Small Moments
by: Woodruff, David P., et al.
Published: (2025)

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

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

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

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

Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation
by: Danait, Ved, et al.
Published: (2025)

Sublinear Metric Steiner Forest via Maximal Independent Set
by: Mahabadi, Sepideh, 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)

Sublinear Time Quantum Sensitivity Sampling
by: Song, Zhao, et al.
Published: (2025)

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

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

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

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

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

Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model
by: Feng, Shiyuan, et al.
Published: (2025)

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

Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette Sparsification
by: Assadi, Sepehr, et al.
Published: (2025)