Cover Image

Halfspaces are hard to test with relative error

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Xi, De, Anindya, Huang, Yizhi, Nadimpalli, Shivam, Servedio, Rocco A., Yang, Tianqi
Format:	Preprint
Published:	2025
Subjects:	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

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

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

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

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

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

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

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

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

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

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

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

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

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

Is nasty noise actually harder than malicious noise?
by: Blanc, Guy, et al.
Published: (2025)

No Price Tags? No Problem: Query Strategies for Unpriced Information
by: Nadimpalli, Shivam, et al.
Published: (2025)

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

Faster exact learning of k-term DNFs with membership and equivalence queries
by: Alman, Josh, et al.
Published: (2025)

DNF Learning via Locally Mixing Random Walks
by: Alman, Josh, et al.
Published: (2025)

Trace reconstruction from local statistical queries
by: Chen, Xi, et al.
Published: (2024)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
by: Heeger, Klaus, et al.
Published: (2024)

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
by: Chen, Xi, et al.
Published: (2026)

Quadratic Speedup for Computing Contraction Fixed Points
by: Chen, Xi, et al.
Published: (2026)

Boolean function monotonicity testing requires (almost) $n^{1/2}$ queries
by: Chen, Mark, et al.
Published: (2025)

The complexity of testing all properties of planar graphs, and the role of isomorphism
by: Basu, Sabyasachi, et al.
Published: (2021)

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

Sketching approximations and LP approximations for finite CSPs are related
by: Singer, Noah G., et al.
Published: (2025)

A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions
by: Chen, Xi, et al.
Published: (2025)

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

Resource Leveling: Complexity of a UET two-processor scheduling variant and related problems
by: Bendotti, Pascale, et al.
Published: (2024)

On the Complexity of Minimizing Energy Consumption of Partitioning DAG Tasks
by: Liu, Wei, et al.
Published: (2024)

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
by: Hirahara, Shuichi, et al.
Published: (2024)

An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem
by: Yang, Yang
Published: (2025)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
by: Yang, Yang
Published: (2024)

Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
by: Nadimpalli, Shivam, et al.
Published: (2024)

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

On the Mysteries of MAX NAE-SAT
by: Brakensiek, Joshua, et al.
Published: (2020)

Better late, then? The hardness of choosing delays to meet passenger demands in temporal graphs
by: Kutner, David C., et al.
Published: (2025)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
by: Kunisky, Dmitriy, et al.
Published: (2024)

Computing the $D$-base and $D$-relation in finite closure systems
by: Adaricheva, Kira, et al.
Published: (2024)