Testing (Subclasses of) Halfspaces

DOI10.1007/978-3-642-16367-8_27MaRDI QIDQ4933385zbMATH OpenOpenAlexFDO

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

Publication date 12 October 2010

Published in Property Testing (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/1721.1/72033

zbMATH Keywords

halfspaceslinear thresholds functions

Mathematics Subject Classification ID

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

Recommendations

• Testing halfspaces
• Testing Halfspaces
• Testing ±1-weight halfspace
• scientific article; zbMATH DE number 1089205
• scientific article; zbMATH DE number 1512855
• Testing and distinguishing sets in Banach spaces
• Testing Hypotheses Concerning Unions of Linear Subspaces
• Testing Halfspaces over Rotation-Invariant Distributions
• Topological test spaces
• Testing the dimension of Hilbert spaces

Cites work

• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• scientific article; zbMATH DE number 3314813 (Why is no real title available?)
• A Bound on the Precision Required to Estimate a Boolean Perceptron from Its Average Satisfying Assignment
• Active learning using arbitrary binary valued queries
• An introduction to support vector machines and other kernel-based learning methods.
• Every linear threshold function has a low-weight approximator
• On generalized constraints and certificates
• On restricted-focus-of-attention learnability of Boolean functions
• Property testing and its connection to learning and approximation
• Testing juntas
• Testing ±1-weight halfspace
• The Perceptron: A Model for Brain Functioning. I
• Threshold circuits of bounded depth

Cited in

(6)

• Adaptivity is exponentially powerful for testing monotonicity of halfspaces
• Distribution-free testing for halfspaces (almost) requires PAC learning
• Testing Halfspaces
• Testing problems with sublearning sample complexity
• Testing ±1-weight halfspace
• Testing halfspaces

This page was built for publication: Testing (Subclasses of) Halfspaces

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