Cover Image

How fast can you find a good hypothesis?

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Aamand, Anders, Aliakbarpour, Maryam, Chen, Justin Y., Silwal, Sandeep
Format:	Preprint
Published:	2025
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

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

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)

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

Statistical-Computational Trade-offs for Density Estimation
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)

Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions
by: Aliakbarpour, Maryam, et al.
Published: (2026)

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

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

Metalearning with Very Few Samples Per Task
by: Aliakbarpour, Maryam, et al.
Published: (2023)

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

Better Private Distribution Testing by Leveraging Unverified Auxiliary Data
by: Aliakbarpour, Maryam, et al.
Published: (2025)

High-Probability Bounds For Heterogeneous Local Differential Privacy
by: Aliakbarpour, Maryam, et al.
Published: (2025)

Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor
by: Aliakbarpour, Maryam, et al.
Published: (2025)

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

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

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

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

Non-iid hypothesis testing: from classical to quantum
by: De Palma, Giacomo, et al.
Published: (2025)

Algorithms with Calibrated Machine Learning Predictions
by: Shen, Judy Hanwen, et al.
Published: (2025)

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

MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation
by: Hayderi, Alexandre, et al.
Published: (2024)

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

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

Do you know what q-means?
by: Cornelissen, Arjan, et al.
Published: (2023)

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

Provably learning a multi-head attention layer
by: Chen, Sitan, et al.
Published: (2024)

Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing
by: Kunisky, Dmitriy
Published: (2024)

Finite Sample Bounds for Learning with Score Matching
by: Smedira, Devin, et al.
Published: (2026)

Optimal Approximate Matrix Multiplication over Sliding Windows
by: Yao, Ziqi, et al.
Published: (2025)

On the Power of Learning-Augmented Search Trees
by: Chen, Jingbang, et al.
Published: (2022)

Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap
by: Karpov, Nikolai, et al.
Published: (2025)

Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions
by: Chen, Yixin, et al.
Published: (2026)

Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint
by: Chen, Yixin, et al.
Published: (2020)

The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits
by: Assadi, Sepehr, et al.
Published: (2023)

Linear Submodular Maximization with Bandit Feedback
by: Chen, Wenjing, et al.
Published: (2024)

The 2020 US Decennial Census is more private than you (might) think
by: Su, Buxin, et al.
Published: (2024)

On the Problem of Best Arm Retention
by: Chen, Houshuang, et al.
Published: (2025)

Minimum-Cost Network Flow with Dual Predictions
by: Chen, Zhiyang, et al.
Published: (2026)