Testing ±1-weight halfspace

DOI10.1007/978-3-642-03685-9_48MaRDI QIDQ3638910zbMATH OpenOpenAlexFDO

Authors Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio

Publication date 28 October 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03685-9_48

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Testing (Subclasses of) Halfspaces
• Testing halfspaces
• Testing Halfspaces
• Adaptivity is exponentially powerful for testing monotonicity of halfspaces
• Learning Boolean halfspaces with small weights from membership queries

Cited in

(11)

• An adaptivity hierarchy theorem for property testing
• Exponentially improved algorithms and lower bounds for testing signed majorities
• An optimal tester for k-Linear
• Testing Halfspaces
• Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
• Testing halfspaces
• Testing (Subclasses of) Halfspaces
• Almost optimal distribution-free junta testing
• Testing Halfspaces over Rotation-Invariant Distributions
• Almost Optimal Testers for Concise Representations.
• Distribution-free testing for halfspaces (almost) requires PAC learning

This page was built for publication: Testing ±1-weight halfspace

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638910)