Testing halfspaces

zbMATH Open1422.68129MaRDI QIDQ4633833FDOQ4633833

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

Publication date: 6 May 2019

Full work available at URL: https://dl.acm.org/citation.cfm?id=1496799

Recommendations

• Testing Halfspaces
• Testing (Subclasses of) Halfspaces
• Testing Halfspaces over Rotation-Invariant Distributions
• Testing ±1-weight halfspace
• Adaptivity is exponentially powerful for testing monotonicity of halfspaces

Mathematics Subject Classification ID

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

Cited In (9)

• Adaptivity is exponentially powerful for testing monotonicity of halfspaces
• Distribution-free testing for halfspaces (almost) requires PAC learning
• Biased halfspaces, noise sensitivity, and local Chernoff inequalities
• Testing (Subclasses of) Halfspaces
• Testing Halfspaces over Rotation-Invariant Distributions
• Testing Halfspaces
• Testing ±1-weight halfspace
• Directed projection graph of \(N\)-dimensional hypercube and subhypercube decomposition of balanced linearly separable Boolean functions
• Halfspace matrices

This page was built for publication: Testing halfspaces

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