Boolean function monotonicity testing requires (almost) $n^{1/2}$ queries

November 06, 2025 ยท The Ethereal ยท ๐Ÿ› arXiv.org

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Mark Chen, Xi Chen, Hao Cui, William Pires, Jonah Stockwell arXiv ID 2511.04558 Category cs.CC: Computational Complexity Cross-listed cs.DM, cs.DS Citations 1 Venue arXiv.org Last Checked 6 months ago
Abstract
We show that for any constant $c>0$, any (two-sided error) adaptive algorithm for testing monotonicity of Boolean functions must have query complexity $ฮฉ(n^{1/2-c})$. This improves the $\tildeฮฉ(n^{1/3})$ lower bound of [CWX17] and almost matches the $\tilde{O}(\sqrt{n})$ upper bound of [KMS18].
Community shame:
Not yet rated
๐Ÿ“„ View on arXiv ๐ŸŒ View on ar5iv ๐Ÿ“‘ PDF ๐ŸŽ‰ Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Computational Complexity