Boolean Function Monotonicity Testing Requires (Almost) n1/2 Queries
Mark Chen, Xi Chen, Hao Cui, William Pires, Jonah Stockwell
2026年份
摘要
We show that for any constant c>0, any (two-sided error) adaptive algorithm for testing monotonicity of Boolean functions must have query complexity Ω(n1/2−c). This improves the Ω(n1/3) lower bound of Chen, Waingarten, and Xie (2017) and almost matches the Õ(√n) upper bound of Khot, Minzer and Safra (2018).
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了每一个公式，引用它的顶会 Paper 也一样。你提问，回答直接引用原文。
它引用的顶会 Paper3
- Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in d-DimensionsHadley Black, Deeparnab Chakrabarty, C. SeshadhriSODA 2020 · 被引用 10 次
- A d1/2+o(1) Monotonicity Tester for Boolean Functions on d-Dimensional HypergridsHadley Black, Deeparnab Chakrabarty, C. SeshadhriFOCS 2023 · 被引用 5 次
- Relative-error monotonicity testingXi Chen, Anindya De, Yizhi Huang, Yuhao Li 等SODA 2025 · 被引用 1 次
相关 Paper
- Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and JuntasXi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli 等SODA 2024
- Approximating the Distance to Monotonicity of Boolean FunctionsRamesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik WaingartenSODA 2020 · 被引用 6 次
- Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity TesterHadley Black, Deeparnab Chakrabarty, C. SeshadhriSTOC 2023 · 被引用 5 次
- New Lower Bounds for Adaptive Tolerant Junta TestingXi Chen, Shyamal PatelFOCS 2023 · 被引用 3 次
- Agnostic proper learning of monotone functions: beyond the black-box correction barrierJane Lange, Arsen VasilyanFOCS 2023 · 被引用 4 次
