Cover Image

Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Aliakbarpour, Maryam, Azizi, Alireza, Stevens, Ria
Format:	Preprint
Published:	2026
Subjects:	Machine Learning Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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)

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

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

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

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

Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms
by: Angelopoulos, Spyros, et al.
Published: (2024)

Prediction-Specific Design of Learning-Augmented Algorithms
by: Li, Sizhe, et al.
Published: (2025)

Matroid Algorithms Under Size-Sensitive Independence Oracles
by: Banihashem, Kiarash, et al.
Published: (2026)

Near-Optimal Algorithms for Omniprediction
by: Okoroafor, Princewill, et al.
Published: (2025)

Learning-Augmented Algorithms with Explicit Predictors
by: Elias, Marek, et al.
Published: (2024)

Towards Optimal Robustness in Learning-Augmented Paging
by: Chen, Peng, et al.
Published: (2026)

Learning-Augmented Streaming Algorithms for Correlation Clustering
by: Dong, Yinhao, et al.
Published: (2025)

Instance-Optimal Uniformity Testing and Tracking
by: Blanc, Guy, et al.
Published: (2025)

Testing Noise Assumptions of Learning Algorithms
by: Goel, Surbhi, et al.
Published: (2025)

Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms
by: Angelopoulos, Spyros, et al.
Published: (2025)

Learning-Augmented Algorithms for $k$-median via Online Learning
by: Hebbar, Anish, et al.
Published: (2026)

A Simple Approximation Algorithm for Optimal Decision Tree
by: Zhuo, Zhengjia, et al.
Published: (2025)

Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms
by: Lechowicz, Adam, et al.
Published: (2023)

Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management
by: Hsieh, Wen-Han, et al.
Published: (2026)

Efficient Discrepancy Testing for Learning with Distribution Shift
by: Chandrasekaran, Gautam, et al.
Published: (2024)

Approximation Algorithms for Combinatorial Optimization with Predictions
by: Antoniadis, Antonios, et al.
Published: (2024)

Online Algorithms with Uncertainty-Quantified Predictions
by: Sun, Bo, et al.
Published: (2023)

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

Binary Search with Distributional Predictions
by: Dinitz, Michael, et al.
Published: (2024)

Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion
by: Veldt, Nate, et al.
Published: (2026)

Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret
by: Harada, Tsubasa, et al.
Published: (2025)

Improving Online Algorithms via ML Predictions
by: Kumar, Ravi, et al.
Published: (2024)

Learning-Augmented Ski Rental with Discrete Distributions: A Bayesian Approach
by: Kang, Bosun, et al.
Published: (2025)

Distribution-Free Sequential Prediction with Abstentions
by: Yu, Jialin, et al.
Published: (2026)

Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions
by: Cheng, Kangke, et al.
Published: (2026)

Ski Rental with Distributional Predictions of Unknown Quality
by: Cui, Qiming, et al.
Published: (2026)

Learning-augmented Maximum Independent Set
by: Braverman, Vladimir, et al.
Published: (2024)

Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds
by: Klivans, Adam R., et al.
Published: (2024)

Exploiting Low-Rank Structure in Max-K-Cut Problems
by: Stevens, Ria, et al.
Published: (2026)

Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets
by: Lee, Russell, et al.
Published: (2022)

On Tradeoffs in Learning-Augmented Algorithms
by: Benomar, Ziyad, et al.
Published: (2025)

Differentially Private and Scalable Estimation of the Network Principal Component
by: Khayatian, Alireza, et al.
Published: (2025)

Learning-Augmented Algorithms for the Bahncard Problem
by: Zhao, Hailiang, et al.
Published: (2024)