An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube

DOI10.1137/13092770XzbMath1339.68308OpenAlexW2515694000MaRDI QIDQ2805510

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) Combinatorial optimization (90C27) Randomized algorithms (68W20)

Related Items (12)

Parameterized property testing of functions ⋮ Quantum and classical query complexities for generalized Deutsch-Jozsa problems ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ Unnamed Item ⋮ Approximating the Noise Sensitivity of a Monotone Boolean Function ⋮ Almost Optimal Distribution-Free Sample-Based Testing of k-Modality ⋮ Quantum algorithms on Walsh transform and Hamming distance for Boolean functions ⋮ Unnamed Item ⋮ Adaptive Boolean Monotonicity Testing in Total Influence Time ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Testing Boolean Functions Properties

Cites Work

• Unnamed Item
• Unnamed Item
• Monotonicity testing and shortest-path routing on the cube
• Property testing lower bounds via communication complexity
• Spot-checkers
• Tolerant property testing and distance approximation
• Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity
• Testing monotonicity over graph products
• Monotonicity testing over general poset domains
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids
• Optimal numberings and isoperimetric problems on graphs
• Testing monotonicity
• On disjoint chains of subsets

This page was built for publication: An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube