On Monotonicity Testing and Boolean Isoperimetric-type Theorems
From MaRDI portal
Publication:4562273
DOI10.1137/16M1065872zbMath1409.68142OpenAlexW2904542722WikidataQ128719347 ScholiaQ128719347MaRDI QIDQ4562273
Shmuel Safra, Subhash A. Khot, Dor Minzer
Publication date: 19 December 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1065872
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Boolean functions (06E30) Randomized algorithms (68W20)
Related Items (16)
Log-Sobolev inequality for the multislice, with applications ⋮ Parameterized property testing of functions ⋮ Quantum and classical query complexities for generalized Deutsch-Jozsa problems ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ An optimal tester for \(k\)-Linear ⋮ Unnamed Item ⋮ Sample-Based High-Dimensional Convexity Testing. ⋮ Adaptive Lower Bound for Testing Monotonicity on the Line ⋮ Almost Optimal Distribution-Free Sample-Based Testing of k-Modality ⋮ Directed isoperimetric theorems for Boolean functions on the hypergrid and an \(\widetilde{O}(n\sqrt{d})\) monotonicity tester ⋮ Isoperimetric inequalities for real-valued functions with applications to monotonicity testing ⋮ Adaptive Boolean Monotonicity Testing in Total Influence Time ⋮ Unnamed Item ⋮ A Polynomial Lower Bound for Testing Monotonicity ⋮ Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity ⋮ Unnamed Item
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
This page was built for publication: On Monotonicity Testing and Boolean Isoperimetric-type Theorems
