A new PAC learning algorithm for k-halfspace intersections with ρ-margin achieves runtime poly(k, ε^{-1}, ρ^{-1}) exp(O(√(n log(1/ρ) log k))), improving prior work and matching lower bounds up to logs.
A note on the sign degree of formulas.arXiv preprint arXiv:0909.4607
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
years
2026 2verdicts
UNVERDICTED 2representative citing papers
Properties constant-query testable classically in the bidirectional bounded-degree directed graph model admit n^{1/2 - Ω(1)} quantum query testers in the unidirectional model, with an almost-matching lower bound.
citing papers explorer
-
Tight Bounds for Learning Polyhedra with a Margin
A new PAC learning algorithm for k-halfspace intersections with ρ-margin achieves runtime poly(k, ε^{-1}, ρ^{-1}) exp(O(√(n log(1/ρ) log k))), improving prior work and matching lower bounds up to logs.
-
Quantum Property Testing for Bounded-Degree Directed Graphs
Properties constant-query testable classically in the bidirectional bounded-degree directed graph model admit n^{1/2 - Ω(1)} quantum query testers in the unidirectional model, with an almost-matching lower bound.