Testing ±1-weight halfspace

DOI10.1007/978-3-642-03685-9_48zbMath1255.68295OpenAlexW2244431488MaRDI QIDQ3638910

Ronitt Rubinfeld, Kevin Matulef, Ryan O'Donnell, 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)

Related Items (7)

An adaptivity hierarchy theorem for property testing ⋮ An optimal tester for \(k\)-Linear ⋮ Almost Optimal Testers for Concise Representations. ⋮ Testing (Subclasses of) Halfspaces ⋮ Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity ⋮ Almost optimal distribution-free junta testing ⋮ Exponentially improved algorithms and lower bounds for testing signed majorities

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