Directed isoperimetric theorems for Boolean functions on the hypergrid and an \(\widetilde{O}(n\sqrt{d})\) monotonicity tester

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Monotonicity testing and shortest-path routing on the cube
Property testing lower bounds via communication complexity
Information theory in property testing and monotonicity testing in higher dimension
Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem
On the strength of comparisons in property testing
Approximating the distance to monotonicity in high dimensions
Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries
Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity
Testing monotonicity over graph products
Monotonicity testing over general poset domains
On Monotonicity Testing and Boolean Isoperimetric-type Theorems
Parameterized property testing of functions
Property Testing on Product Distributions
Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
A Polynomial Lower Bound for Testing Monotonicity
Adaptive Boolean Monotonicity Testing in Total Influence Time
Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in d-Dimensions
Approximating the Distance to Monotonicity of Boolean Functions
L _p -testing
Estimating the distance to a monotone function
A o(n) monotonicity tester for boolean functions over the hypercube
Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids
Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners
Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
Testing monotonicity
On disjoint chains of subsets

This page was built for publication: Directed isoperimetric theorems for Boolean functions on the hypergrid and an \(\widetilde{O}(n\sqrt{d})\) monotonicity tester