pipette
ESEspañol

No Perfect Randomized Composition

Alexander Meiburg

Preprint

In the authors' words

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 such that This result requires first separating linearized query complexity , as well as noisy randomized query complexity , from standard randomized query complexity . 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 , max-conflict , and linearised query complexity . 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 by the maximal factor . The total--total composition separation is also formalized in Lean.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 23. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 56 pages