A polynomial lower bound for testing monotonicity

DOI10.1145/2897518.2897567zbMath1373.68234arXiv1511.05053OpenAlexW2267350596MaRDI QIDQ5361899

Eric Blais, Aleksandrs Belovs

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.05053

zbMATH Keywords

property testingadaptivity of query algorithmsTalagrand's random DNF

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (16)

Parameterized property testing of functions ⋮ On Monotonicity Testing and Boolean Isoperimetric-type Theorems ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ An optimal tester for \(k\)-Linear ⋮ Unnamed Item ⋮ Approximating the Noise Sensitivity of a Monotone Boolean Function ⋮ Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces ⋮ Adaptive Lower Bound for Testing Monotonicity on the Line ⋮ Almost Optimal Distribution-Free Sample-Based Testing of k-Modality ⋮ Almost Optimal Testers for Concise Representations. ⋮ Unnamed Item ⋮ Adaptive Boolean Monotonicity Testing in Total Influence Time ⋮ Almost optimal distribution-free junta testing ⋮ A Polynomial Lower Bound for Testing Monotonicity ⋮ Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity ⋮ Unnamed Item

This page was built for publication: A polynomial lower bound for testing monotonicity