An o(n) monotonicity tester for Boolean functions over the hypercube
From MaRDI portal
Publication:2805510
DOI10.1137/13092770XzbMATH Open1339.68308OpenAlexW2515694000MaRDI QIDQ2805510FDOQ2805510
Authors: Deeparnab Chakrabarty, C. Seshadhri 
Publication date: 12 May 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/13092770x
Recommendations
- A \(o(n)\) monotonicity tester for Boolean functions over the hypercube
- A \(o(d) \cdot \operatorname{polylog} n\) monotonicity tester for Boolean functions over the hypergrid \([n]^d\)
- Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
- On Monotonicity Testing and Boolean Isoperimetric-type Theorems
- Approximating the distance to monotonicity of Boolean functions
Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Combinatorial optimization (90C27)
Cites Work
- Spot-checkers
- Testing monotonicity over graph products
- Monotonicity testing over general poset domains
- Title not available (Why is that?)
- Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
- Testing monotonicity
- Optimal numberings and isoperimetric problems on graphs
- Title not available (Why is that?)
- Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
- Monotonicity testing and shortest-path routing on the cube
- On disjoint chains of subsets
- Property testing lower bounds via communication complexity
- Tolerant property testing and distance approximation
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Cited In (19)
- Adaptive Boolean Monotonicity Testing in Total Influence Time
- Quantum algorithms on Walsh transform and Hamming distance for Boolean functions
- Testing Boolean Functions Properties
- Title not available (Why is that?)
- Title not available (Why is that?)
- Testing monotonicity
- Approximating the Noise Sensitivity of a Monotone Boolean Function
- Quantum and classical query complexities for generalized Deutsch-Jozsa problems
- Title not available (Why is that?)
- An optimal lower bound for monotonicity testing over hypergrids
- Approximating the distance to monotonicity of Boolean functions
- A counterexample to a directed KKL inequality
- A \(o(n)\) monotonicity tester for Boolean functions over the hypercube
- On Monotonicity Testing and Boolean Isoperimetric-type Theorems
- Isoperimetric inequalities for real-valued functions with applications to monotonicity testing
- Title not available (Why is that?)
- Parameterized property testing of functions
- Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
- Title not available (Why is that?)
This page was built for publication: An \(o(n)\) monotonicity tester for Boolean functions over the hypercube
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2805510)
