Skip to content
Preprint

Composition Theorem for Randomized Query Complexity

Nov 2026 · 0 citations · 18 references
Computer Science

Abstract

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) = \Omega\!\left(\frac{R(f)R(g)}{\log(n+1)}\right), \] where $n$ is the input size for $f$.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.