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

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

(23)

Adaptive Boolean Monotonicity Testing in Total Influence Time
Quantum algorithms on Walsh transform and Hamming distance for Boolean functions
Optimal unateness testers for real-valued functions: adaptivity helps
scientific article; zbMATH DE number 7559095 (Why is no real title available?)
scientific article; zbMATH DE number 6395191 (Why is no real title available?)
Testing \(k\)-monotonicity. The rise and fall of Boolean functions
Testing k-monotonicity
Testing monotonicity
Approximating the Noise Sensitivity of a Monotone Boolean Function
Quantum and classical query complexities for generalized Deutsch-Jozsa problems
Testing Boolean functions properties
An optimal lower bound for monotonicity testing over hypergrids
A \(o(d) \cdot \operatorname{polylog} n\) monotonicity tester for Boolean functions over the hypergrid \([n]^d\)
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
Parameterized property testing of functions
Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
Flipping out with many flips: hardness of testing \(k\)-monotonicity
Nearly optimal bounds for sample-based testing and learning of k-monotone functions
On the houdré-tetali conjecture about an isoperimetric constant of graphs

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)