arXiv · Oct 22, 2026
No Perfect Randomized Composition
By Alexander Meiburg
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∘ g) =Θ(frac1log R(g))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 χ, and linearised query complexity LR. We show that AND-of-ORs separates conflict χ from max-conflict χ 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.