On Monotonicity Testing and Boolean Isoperimetric-type Theorems
From MaRDI portal
Publication:4562273
DOI10.1137/16M1065872zbMath1409.68142MaRDI QIDQ4562273
Shmuel Safra, Subhash A. Khot, Dor Minzer
Publication date: 19 December 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68R05: Combinatorics in computer science
06E30: Boolean functions
68W20: Randomized algorithms
Related Items
Cites Work
- Unnamed Item
- Monotonicity testing and shortest-path routing on the cube
- Correlation inequalities on some partially ordered sets
- Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem
- An Optimal Lower Bound for Monotonicity Testing over Hypergrids
- 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
- Monotonicity testing over general poset domains
- A polynomial lower bound for testing monotonicity
- 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
- Testing monotonicity
- On disjoint chains of subsets