Cover Image

Is nasty noise actually harder than malicious noise?

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Blanc, Guy, Huang, Yizhi, Malkin, Tal, Servedio, Rocco A.
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

MAX BISECTION might be harder to approximate than MAX CUT
by: Brakensiek, Joshua, et al.
Published: (2025)

Sparsifying Suprema of Gaussian Processes
by: De, Anindya, et al.
Published: (2024)

Halfspaces are hard to test with relative error
by: Chen, Xi, et al.
Published: (2025)

Sublinear-query relative-error testing of halfspaces
by: Chen, Xi, et al.
Published: (2026)

Adaptive and oblivious statistical adversaries are equivalent
by: Blanc, Guy, et al.
Published: (2024)

Learning Functions of Halfspaces
by: Alman, Josh, et al.
Published: (2026)

A Distributional-Lifting Theorem for PAC Learning
by: Blanc, Guy, et al.
Published: (2025)

Computational-Statistical Tradeoffs from NP-hardness
by: Blanc, Guy, et al.
Published: (2025)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
by: Blanc, Guy, et al.
Published: (2024)

Detecting Low-Degree Truncation
by: De, Anindya, et al.
Published: (2024)

DNF formulas are efficiently testable with relative error
by: Chen, Xi, et al.
Published: (2026)

Model-agnostic super-resolution in high dimensions
by: Chen, Xi, et al.
Published: (2025)

Samplability makes learning easier
by: Blanc, Guy, et al.
Published: (2025)

Testing noisy low-degree polynomials for sparsity
by: Bao, Yiqiao, et al.
Published: (2025)

Lower Bounds for Convexity Testing
by: Chen, Xi, et al.
Published: (2024)

Relative-error monotonicity testing
by: Chen, Xi, et al.
Published: (2024)

Testing Sumsets is Hard
by: Chen, Xi, et al.
Published: (2024)

Testing Convex Truncation
by: De, Anindya, et al.
Published: (2023)

Relative-error testing of conjunctions and decision lists
by: Chen, Xi, et al.
Published: (2025)

Testing Juntas and Junta Subclasses with Relative Error
by: Chen, Xi, et al.
Published: (2025)

Unifying Formal Explanations: A Complexity-Theoretic Perspective
by: Bassan, Shahaf, et al.
Published: (2026)

Relative-error unateness testing
by: Chen, Xi, et al.
Published: (2025)

Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
by: Golowich, Noah, et al.
Published: (2024)

On Computationally Efficient Multi-Class Calibration
by: Gopalan, Parikshit, et al.
Published: (2024)

Efficient and Private Property Testing via Indistinguishability
by: Dwork, Cynthia, et al.
Published: (2025)

Feature Selection and Junta Testing are Statistically Equivalent
by: Beretta, Lorenzo, et al.
Published: (2025)

Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection
by: Sato, Atsuki, et al.
Published: (2025)

Efficient Turing Machine Simulation with Transformers
by: Li, Qian, et al.
Published: (2025)

Rate-optimal community detection near the KS threshold via node-robust algorithms
by: Ding, Jingqiu, et al.
Published: (2025)

Learning-Augmented Algorithms for Boolean Satisfiability
by: Attias, Idan, et al.
Published: (2025)

The Computational Complexity of Almost Stable Clustering with Penalties
by: Khodamoradi, Kamyar, et al.
Published: (2025)

Supersimulators
by: Dwork, Cynthia, et al.
Published: (2025)

Superconstant Inapproximability of Decision Tree Learning
by: Koch, Caleb, et al.
Published: (2024)

Exact and Approximate Algorithms for Polytree Learning
by: Harviainen, Juha, et al.
Published: (2026)

Differentially Private Verification of Distribution Properties
by: Du, Elbert, et al.
Published: (2026)

Fast decision tree learning solves hard coding-theoretic problems
by: Koch, Caleb, et al.
Published: (2024)

Private graphon estimation via sum-of-squares
by: Chen, Hongjie, et al.
Published: (2024)

Low-Degree Method Fails to Predict Robust Subspace Recovery
by: Jia, He, et al.
Published: (2026)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
by: Gopalan, Parikshit, et al.
Published: (2024)

On the Power of Interactive Proofs for Learning
by: Gur, Tom, et al.
Published: (2024)