No Perfect Randomized Composition
Alexander Meiburg
cs.CC
Oct 22, 2026 · v1
math.CO
TL;DR
The main total–total composition separation (a little-o statement on a subsequence of the construction) is machine-checked in Lean 4.
Abstract
Does computing a composition of total Boolean functions require the product of the randomized query complexities of its factors? We give a negative answer. There are families of total functions $f,g$ such that $R(f\circ g) =Θ\!\left(\frac1{\log R(g)}\right)R(f)R(g)$ This result requires first separating linearized query complexity $\LR$, as well as noisy randomized query complexity $noisyR$, from standard randomized query complexity $R$. Both constructions essentially come from totalizing existing partial function separations, albeit via different techniques. By adapting these techniques, we also construct total functions separating every adjacent pair in the chain from sabotage $RS$, max-conflict $\barχ$, and linearised query complexity $LR$. We show that AND-of-ORs separates conflict $χ$ from max-conflict $\barχ$ complexity and makes conflict and sabotage incomparable. Finally, randomized complexity can be smaller than its composition limit $R^*$ by the maximal factor $Θ(\log R)$. The total–total composition separation is also formalized in Lean.
Problem
The question is whether the randomized query complexity of a composition of total Boolean functions is always at least a constant times the product of the factors' complexities, R(f∘g) ≥ c·R(f)R(g). The inequality was known to fail for partial functions but was open for total ones.
Approach
The construction first separates linearized query complexity and noisy randomized query complexity from standard randomized complexity using total functions. These are obtained by totalizing known partial-function separations via cheat-sheet certificate arrays, linear encodings and exact one-sided detectors. A certificate-based outer function W_q is combined with an inner function that has a cheap weak evaluator. The same techniques yield separations along the chain of sabotage, conflict, max-conflict, linearized and randomized complexity.
Results
There are total f and g with R(f∘g) = Θ(1/log R(g))·R(f)R(g), so perfect randomized composition fails for total functions. The paper also gives total separations between adjacent measures in the chain, shows that AND-of-ORs separates conflict from max-conflict complexity, and shows that R can be smaller than its composition limit R* by a Θ(log R) factor. The main total–total result is formalized in Lean 4.
