A Polynomial Lower Bound for Testing Monotonicity

DOI10.1137/16M1097006MaRDI QIDQ4994983

Eric Blais, Aleksandrs Belovs

Publication date: 22 June 2021

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

noise sensitivitymonotone Boolean functionsproperty testingTalagrand's random CNF

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation of linear threshold functions
• Monotonicity testing and shortest-path routing on the cube
• Property testing lower bounds via communication complexity
• On the distributional complexity of disjointness
• How much are increasing sets positively correlated?
• Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries
• The Chow Parameters Problem
• Testing Halfspaces
• Monotonicity testing over general poset domains
• On the noise sensitivity of monotone functions
• On Monotonicity Testing and Boolean Isoperimetric-type Theorems
• Transitive-Closure Spanners
• Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
• Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces
• L _p -testing
• A polynomial lower bound for testing monotonicity
• Approximation by DNF: Examples and Counterexamples
• A o(n) monotonicity tester for boolean functions over the hypercube
• Families of Non-disjoint subsets
• Testing monotonicity