:: Library Catalog

Image de couverture de livre

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Blanc, Guy, Huang, Yizhi, Malkin, Tal, Servedio, Rocco A.
Format:	Preprint
Publié:	2025
Sujets:	Machine Learning Computational Complexity Data Structures and Algorithms
Accès en ligne:	https://arxiv.org/abs/2511.09763
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Sparsifying Suprema of Gaussian Processes
par: De, Anindya, et autres
Publié: (2024)

Halfspaces are hard to test with relative error
par: Chen, Xi, et autres
Publié: (2025)

Sublinear-query relative-error testing of halfspaces
par: Chen, Xi, et autres
Publié: (2026)

Adaptive and oblivious statistical adversaries are equivalent
par: Blanc, Guy, et autres
Publié: (2024)

MAX BISECTION might be harder to approximate than MAX CUT
par: Brakensiek, Joshua, et autres
Publié: (2025)

Learning Functions of Halfspaces
par: Alman, Josh, et autres
Publié: (2026)

Model-agnostic super-resolution in high dimensions
par: Chen, Xi, et autres
Publié: (2025)

A Distributional-Lifting Theorem for PAC Learning
par: Blanc, Guy, et autres
Publié: (2025)

Computational-Statistical Tradeoffs from NP-hardness
par: Blanc, Guy, et autres
Publié: (2025)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
par: Blanc, Guy, et autres
Publié: (2024)

Detecting Low-Degree Truncation
par: De, Anindya, et autres
Publié: (2024)

DNF formulas are efficiently testable with relative error
par: Chen, Xi, et autres
Publié: (2026)

Samplability makes learning easier
par: Blanc, Guy, et autres
Publié: (2025)

Relative-error monotonicity testing
par: Chen, Xi, et autres
Publié: (2024)

Testing noisy low-degree polynomials for sparsity
par: Bao, Yiqiao, et autres
Publié: (2025)

Lower Bounds for Convexity Testing
par: Chen, Xi, et autres
Publié: (2024)

Testing Sumsets is Hard
par: Chen, Xi, et autres
Publié: (2024)

Testing Convex Truncation
par: De, Anindya, et autres
Publié: (2023)

Relative-error testing of conjunctions and decision lists
par: Chen, Xi, et autres
Publié: (2025)

Testing Juntas and Junta Subclasses with Relative Error
par: Chen, Xi, et autres
Publié: (2025)

Relative-error unateness testing
par: Chen, Xi, et autres
Publié: (2025)

Unifying Formal Explanations: A Complexity-Theoretic Perspective
par: Bassan, Shahaf, et autres
Publié: (2026)

On Computationally Efficient Multi-Class Calibration
par: Gopalan, Parikshit, et autres
Publié: (2024)

Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
par: Golowich, Noah, et autres
Publié: (2024)

Efficient and Private Property Testing via Indistinguishability
par: Dwork, Cynthia, et autres
Publié: (2025)

Feature Selection and Junta Testing are Statistically Equivalent
par: Beretta, Lorenzo, et autres
Publié: (2025)

Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection
par: Sato, Atsuki, et autres
Publié: (2025)

Efficient Turing Machine Simulation with Transformers
par: Li, Qian, et autres
Publié: (2025)

Rate-optimal community detection near the KS threshold via node-robust algorithms
par: Ding, Jingqiu, et autres
Publié: (2025)

Learning-Augmented Algorithms for Boolean Satisfiability
par: Attias, Idan, et autres
Publié: (2025)

The Computational Complexity of Almost Stable Clustering with Penalties
par: Khodamoradi, Kamyar, et autres
Publié: (2025)

Supersimulators
par: Dwork, Cynthia, et autres
Publié: (2025)

Superconstant Inapproximability of Decision Tree Learning
par: Koch, Caleb, et autres
Publié: (2024)

Exact and Approximate Algorithms for Polytree Learning
par: Harviainen, Juha, et autres
Publié: (2026)

Differentially Private Verification of Distribution Properties
par: Du, Elbert, et autres
Publié: (2026)

Fast decision tree learning solves hard coding-theoretic problems
par: Koch, Caleb, et autres
Publié: (2024)

Private graphon estimation via sum-of-squares
par: Chen, Hongjie, et autres
Publié: (2024)

Low-Degree Method Fails to Predict Robust Subspace Recovery
par: Jia, He, et autres
Publié: (2026)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
par: Gopalan, Parikshit, et autres
Publié: (2024)

On the Power of Interactive Proofs for Learning
par: Gur, Tom, et autres
Publié: (2024)