Testing halfspaces

MaRDI QIDQ4633833zbMATH OpenFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(9)

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