arXiv:2611.08574 · v1

Composition Theorem for Randomized Query Complexity

首次提交 2026-11-06 02:37

版本更新 2026-11-06 02:37

雷达观测 2026-11-09 10:16

摘要

For bounded-error randomized query complexity, we resolve the composition conjecture up to logarithmic factors. The general upper bound $R(f\circ g) = O\!\left(R(f)R(g)\log(R(f)+1)\right)$ was already known. Although Meiburg recently disproved constant-factor multiplicative composition for total Boolean functions, the conjecture allowing polylogarithmic losses remained open. We settle this question by proving that, for all (possibly partial) Boolean functions $f$ and $g$, $$R(f\circ g) = Ω\!\left(\frac{R(f)R(g)}{\log(n+1)}\right),$$ where $n$ is the input size for $f$.

作者备注：21 pages