{"id":"arxiv/2610.31638","url":"https://arxiv.org/abs/2610.31638","tags":["cs.CC","math.CO"],"score":0,"title":"No Perfect Randomized Composition","domain":"cs.CC","source":"arxiv","authors":["Alexander Meiburg"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-22","reactions":{}}