A o(n) monotonicity tester for boolean functions over the hypercube
From MaRDI portal
Publication:5495811
DOI10.1145/2488608.2488660zbMath1293.90054arXiv1302.4536OpenAlexW2053267965MaRDI QIDQ5495811
C. Seshadhri, Deeparnab Chakrabarty
Publication date: 7 August 2014
Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1302.4536
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Randomized algorithms (68W20)
Related Items (11)
On Monotonicity Testing and Boolean Isoperimetric-type Theorems ⋮ An optimal tester for \(k\)-Linear ⋮ Unnamed Item ⋮ Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces ⋮ Adaptive Lower Bound for Testing Monotonicity on the Line ⋮ Almost Optimal Testers for Concise Representations. ⋮ Unnamed Item ⋮ Almost optimal distribution-free junta testing ⋮ A Polynomial Lower Bound for Testing Monotonicity ⋮ Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity ⋮ Unnamed Item
This page was built for publication: A o(n) monotonicity tester for boolean functions over the hypercube
