Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
From MaRDI portal
Publication:4977999
DOI10.1145/3055399.3055461zbMath1370.68322arXiv1702.06997OpenAlexW2593853527MaRDI QIDQ4977999
Jinyu Xie, Xi Chen, Erik Waingarten
Publication date: 17 August 2017
Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1702.06997
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Related Items (12)
Approximating the distance to monotonicity of Boolean functions ⋮ An optimal tester for \(k\)-Linear ⋮ Unnamed Item ⋮ 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
This page was built for publication: Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
