An o(n) monotonicity tester for Boolean functions over the hypercube

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

zbMATH Keywords

Boolean functionsmonotonicity testingdirected isoperimetry

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Combinatorial optimization (90C27)

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

Cites work

• scientific article; zbMATH DE number 3503316 (Why is no real title available?)
• scientific article; zbMATH DE number 1418269 (Why is no real title available?)
• Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Monotonicity testing and shortest-path routing on the cube
• Monotonicity testing over general poset domains
• On disjoint chains of subsets
• Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
• Optimal numberings and isoperimetric problems on graphs
• Property testing lower bounds via communication complexity
• Spot-checkers
• Testing monotonicity
• Testing monotonicity over graph products
• Tolerant property testing and distance approximation

Cited in

(21)

• Testing \(k\)-monotonicity. The rise and fall of Boolean functions
• Parameterized property testing of functions
• A \(o(n)\) monotonicity tester for Boolean functions over the hypercube
• Optimal unateness testers for real-valued functions: adaptivity helps
• Approximating the Noise Sensitivity of a Monotone Boolean Function
• scientific article; zbMATH DE number 7559095 (Why is no real title available?)
• Quantum algorithms on Walsh transform and Hamming distance for Boolean functions
• Adaptive Boolean Monotonicity Testing in Total Influence Time
• On Monotonicity Testing and Boolean Isoperimetric-type Theorems
• scientific article; zbMATH DE number 6395191 (Why is no real title available?)
• Testing Boolean functions properties
• Quantum and classical query complexities for generalized Deutsch-Jozsa problems
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Isoperimetric inequalities for real-valued functions with applications to monotonicity testing
• Approximating the distance to monotonicity of Boolean functions
• Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
• Testing monotonicity
• A \(o(d) \cdot \operatorname{polylog} n\) monotonicity tester for Boolean functions over the hypergrid \([n]^d\)
• Testing \(k\)-monotonicity
• A counterexample to a directed KKL inequality
• An optimal lower bound for monotonicity testing over hypergrids

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)