{"ID":2845430,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.04558","arxiv_id":"2511.04558","title":"Boolean function monotonicity testing requires (almost) $n^{1/2}$ queries","abstract":"We show that for any constant $c\u003e0$, 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].","short_abstract":"We show that for any constant $c\u003e0$, 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].","url_abs":"https://arxiv.org/abs/2511.04558","url_pdf":"https://arxiv.org/pdf/2511.04558v2","authors":"[\"Mark Chen\",\"Xi Chen\",\"Hao Cui\",\"William Pires\",\"Jonah Stockwell\"]","published":"2025-11-06T17:08:33Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DM\",\"cs.DS\"]","methods":"[]","has_code":false}