Image de couverture de livre

Simple and Optimal Sublinear Algorithms for Mean Estimation

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Bertolotti, Beatrice, Russo, Matteo, Schwiegelshohn, Chris, Shyam, Sudarshan
Format:	Preprint
Publié:	2024
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
par: Bansal, Nikhil, et autres
Publié: (2024)

Sublinear Algorithms for Estimating Single-Linkage Clustering Costs
par: Peng, Pan, et autres
Publié: (2025)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
par: Cohen-Addad, Vincent, et autres
Publié: (2025)

Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette Sparsification
par: Assadi, Sepehr, et autres
Publié: (2025)

Almost-Optimal Sublinear Additive Spanners
par: Tan, Zihan, et autres
Publié: (2023)

A Tight VC-Dimension Analysis of Clustering Coresets with Applications
par: Cohen-Addad, Vincent, et autres
Publié: (2025)

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
par: Cohen-Addad, Vincent, et autres
Publié: (2022)

Sublinear Algorithms for TSP via Path Covers
par: Behnezhad, Soheil, et autres
Publié: (2023)

Settling Time vs. Accuracy Tradeoffs for Clustering Big Data
par: Draganov, Andrew, et autres
Publié: (2024)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
par: Dai, Jiangqi, et autres
Publié: (2025)

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring
par: Ferber, Asaf, et autres
Publié: (2025)

Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
par: Narayanan, Shyam, et autres
Publié: (2024)

Improved Sublinear-time Moment Estimation using Weighted Sampling
par: Bhattacharya, Anup, et autres
Publié: (2025)

Near-Optimal Bounds for Parameterized Euclidean k-means
par: Cohen-Addad, Vincent, et autres
Publié: (2026)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
par: Cohen-Addad, Vincent, et autres
Publié: (2026)

Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models
par: Huang, Zengfeng, et autres
Publié: (2025)

Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal
par: Wang, Hanzhi
Publié: (2024)

Optimally Interpolating between Ex-Ante Fairness and Welfare
par: Høgsgaard, Mikael Møller, et autres
Publié: (2023)

Computing String Covers in Sublinear Time
par: Radoszewski, Jakub, et autres
Publié: (2024)

On Solving Linear Systems in Sublinear Time
par: Andoni, Alexandr, et autres
Publié: (2018)

Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation
par: Chen, Yixin, et autres
Publié: (2025)

A Simple, Nearly-Optimal Algorithm for Differentially Private All-Pairs Shortest Distances
par: Campbell, Jesse, et autres
Publié: (2024)

Improved Bounds with a Simple Algorithm for Edge Estimation for Graphs of Unknown Size
par: Chanda, Debarshi
Publié: (2025)

Sublinear Space Graph Algorithms in the Continual Release Model
par: Epasto, Alessandro, et autres
Publié: (2024)

Sublinear Time Algorithm for Online Weighted Bipartite Matching
par: Hu, Hang, et autres
Publié: (2022)

Near-Optimal Trace Reconstruction for Mildly Separated Strings
par: Aamand, Anders, et autres
Publié: (2024)

Solving the Correlation Cluster LP in Sublinear Time
par: Cao, Nairen, et autres
Publié: (2025)

Sublinear Edge Fault Tolerant Spanners for Hypergraphs
par: He, Jialin, et autres
Publié: (2025)

Counting Distinct Square Substrings in Sublinear Time
par: Charalampopoulos, Panagiotis, et autres
Publié: (2025)

Sublinear Spectral Clustering Oracle with Little Memory
par: Shen, Ranran, et autres
Publié: (2026)

Simple and Faster Algorithms for Knapsack
par: He, Qizheng, et autres
Publié: (2023)

Lempel-Ziv (LZ77) Factorization in Sublinear Time
par: Kempa, Dominik, et autres
Publié: (2024)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
par: Goranci, Gramoz, et autres
Publié: (2023)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
par: Bernstein, Aaron, et autres
Publié: (2025)

Sublinear Random Access Generators for Preferential Attachment Graphs
par: Even, Guy, et autres
Publié: (2016)

Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time
par: Eden, Talya, et autres
Publié: (2025)

Maximal Palindromes in MPC: Simple and Optimal
par: Pissis, Solon P.
Publié: (2025)

Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation
par: Danait, Ved, et autres
Publié: (2025)

A Simple Approximation Algorithm for Optimal Decision Tree
par: Zhuo, Zhengjia, et autres
Publié: (2025)

Sublinear Metric Steiner Forest via Maximal Independent Set
par: Mahabadi, Sepideh, et autres
Publié: (2025)