Testing Halfspaces
From MaRDI portal
Publication:3053158
DOI10.1137/070707890zbMath1207.68167OpenAlexW2914539165MaRDI QIDQ3053158
Ryan O'Donnell, Ronitt Rubinfeld, Kevin Matulef, Rocco A. Servedio
Publication date: 4 November 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/5f4953286670c8215af069e4d9e9e0b85c74f29b
Related Items
Biased halfspaces, noise sensitivity, and local Chernoff inequalities, Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces, Improved approximation of linear threshold functions, Half-Spaces with Influential Variable, An optimal tester for \(k\)-Linear, Efficiently testing sparse \(\text{GF}(2)\) polynomials, Sample-Based High-Dimensional Convexity Testing., Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces, Almost Optimal Testers for Concise Representations., On the correlation of increasing families, A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry, A Canonical Form for Testing Boolean Function Properties, Almost optimal distribution-free junta testing, A unified framework for testing linear‐invariant properties, A Polynomial Lower Bound for Testing Monotonicity, Unnamed Item, Exponentially improved algorithms and lower bounds for testing signed majorities
