Cover Image

Statistical-Computational Trade-offs for Density Estimation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Aamand, Anders, Andoni, Alexandr, Chen, Justin Y., Indyk, Piotr, Narayanan, Shyam, Silwal, Sandeep, Xu, Haike
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Bi-metric Framework for Fast Similarity Search
by: Xu, Haike, et al.
Published: (2024)

On the Structure of Replicable Hypothesis Testers
by: Aamand, Anders, et al.
Published: (2025)

How fast can you find a good hypothesis?
by: Aamand, Anders, et al.
Published: (2025)

Skirting Additive Error Barriers for Private Turnstile Streams
by: Aamand, Anders, et al.
Published: (2026)

Improved Approximations for Hard Graph Problems using Predictions
by: Aamand, Anders, et al.
Published: (2025)

Learning-Augmented Frequent Directions
by: Aamand, Anders, et al.
Published: (2025)

Optimal Algorithms for Augmented Testing of Discrete Distributions
by: Aliakbarpour, Maryam, et al.
Published: (2024)

Near-Optimal Trace Reconstruction for Mildly Separated Strings
by: Aamand, Anders, et al.
Published: (2024)

Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
by: Aamand, Anders, et al.
Published: (2025)

Differentially Private Gomory-Hu Trees
by: Aamand, Anders, et al.
Published: (2024)

Even Faster Kernel Matrix Linear Algebra via Density Estimation
by: Shah, Rikhav, et al.
Published: (2025)

Graph-Based Algorithms for Diverse Similarity Search
by: Anand, Piyush, et al.
Published: (2025)

Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors
by: Chatziafratis, Vaggos, et al.
Published: (2023)

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

Better and Simpler Lower Bounds for Differentially Private Statistical Estimation
by: Narayanan, Shyam
Published: (2023)

Even Faster Algorithm for the Chamfer Distance
by: Feng, Ying, et al.
Published: (2025)

Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
by: Silwal, Sandeep, et al.
Published: (2025)

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

Improved algorithms for learning quantum Hamiltonians, via flat polynomials
by: Narayanan, Shyam
Published: (2024)

Robustness Implies Privacy in Statistical Estimation
by: Hopkins, Samuel B., et al.
Published: (2022)

Efficiently Computing Similarities to Private Datasets
by: Backurs, Arturs, et al.
Published: (2024)

A Framework for Building Data Structures from Communication Protocols
by: Andoni, Alexandr, et al.
Published: (2025)

Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems
by: Alman, Josh, et al.
Published: (2024)

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

Hashing for Sampling-Based Estimation
by: Aamand, Anders, et al.
Published: (2024)

Robust Streaming Against Low-Memory Adversaries
by: Ben-Eliezer, Omri, et al.
Published: (2025)

Efficient Algorithms for Adversarially Robust Approximate Nearest Neighbor Search
by: Andoni, Alexandr, et al.
Published: (2026)

Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
by: Narayanan, Shyam, et al.
Published: (2024)

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
by: Gao, Jie, et al.
Published: (2025)

Nearly Optimal Attention Coresets
by: Liberty, Edo, et al.
Published: (2026)

Online Sorting and Translational Packing of Convex Polygons
by: Aamand, Anders, et al.
Published: (2021)

Sample-Efficient Private Learning of Mixtures of Gaussians
by: Ashtiani, Hassan, et al.
Published: (2024)

Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares
by: Chen, Hongjie, et al.
Published: (2024)

Differentially Private Quantiles with Smaller Error
by: Imola, Jacob, et al.
Published: (2025)

On Sketching Quadratic Forms
by: Andoni, Alexandr, et al.
Published: (2015)

Dimension Reduction for Clustering: The Curious Case of Discrete Centers
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

Computational and Statistical Hardness of Calibration Distance
by: Qiao, Mingda
Published: (2026)

Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
by: Chen, Hongjie, et al.
Published: (2024)

Statistical-Computational Trade-offs for Recursive Adaptive Partitioning Estimators
by: Tan, Yan Shuo, et al.
Published: (2024)

New Statistical and Computational Results for Learning Junta Distributions
by: Beretta, Lorenzo
Published: (2025)