On Monotonicity Testing and Boolean Isoperimetric-type Theorems

DOI10.1137/16M1065872zbMath1409.68142OpenAlexW2904542722MaRDI 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

zbMATH Keywords

Boolean functionsproperty testingmonotonicity testingBoolean isoperimetry

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Boolean functions (06E30) Randomized algorithms (68W20)

Related Items (14)

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 ⋮ 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