Copertina

Learning Functions of Halfspaces

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Alman, Josh, Patel, Shyamal, Servedio, Rocco A.
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

Asymptotic Rank Speedup Theorems, Revisited
di: Alman, Josh, et al.
Pubblicazione: (2026)

Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum
di: Alman, Josh, et al.
Pubblicazione: (2025)

A Refined Laser Method and Faster Matrix Multiplication
di: Alman, Josh, et al.
Pubblicazione: (2020)

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

Detecting Low-Degree Truncation
di: De, Anindya, et al.
Pubblicazione: (2024)

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

Lower Bounds for Convexity Testing
di: Chen, Xi, et al.
Pubblicazione: (2024)

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

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
di: Alman, Josh, et al.
Pubblicazione: (2024)

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

Testing Sumsets is Hard
di: Chen, Xi, et al.
Pubblicazione: (2024)

More Asymmetry Yields Faster Matrix Multiplication
di: Alman, Josh, et al.
Pubblicazione: (2024)

Testing Convex Truncation
di: De, Anindya, et al.
Pubblicazione: (2023)

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

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

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

Sparsifying Suprema of Gaussian Processes
di: De, Anindya, et al.
Pubblicazione: (2024)

Relative-error unateness testing
di: Chen, Xi, et al.
Pubblicazione: (2025)

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

Relative-error monotonicity testing
di: Chen, Xi, et al.
Pubblicazione: (2024)

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

Maximization of Approximately Submodular Functions
di: Horel, Thibaut, et al.
Pubblicazione: (2024)

Size Minimization For Multi-Output AND-Functions
di: Armbruster, Susanne
Pubblicazione: (2024)

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
di: Sato, Atsuki, et al.
Pubblicazione: (2024)

Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity
di: Tate, Elise, et al.
Pubblicazione: (2025)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
di: Jansen, Bart M. P., et al.
Pubblicazione: (2026)

Hardness of Learning Boolean Functions from Label Proportions
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2024)

A Simple Proof that Ricochet Robots is PSPACE-Complete
di: Balanza-Martinez, Jose, et al.
Pubblicazione: (2024)

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges
di: Frei, Fabian, et al.
Pubblicazione: (2024)

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
di: Frei, Fabian, et al.
Pubblicazione: (2025)

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
di: Bai, Tian, et al.
Pubblicazione: (2026)

Algorithms and Hardness for Estimating Statistical Similarity
di: Bhattacharyya, Arnab, et al.
Pubblicazione: (2025)

Computational Explorations of Total Variation Distance
di: Bhattacharyya, Arnab, et al.
Pubblicazione: (2024)

Neighborhood-Aware Graph Labeling Problem
di: Shahverdikondori, Mohammad, et al.
Pubblicazione: (2026)

Lazy Kronecker Product
di: Song, Zhao
Pubblicazione: (2026)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
di: Nederlof, Jesper
Pubblicazione: (2026)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
di: Jiang, Cheng, et al.
Pubblicazione: (2026)