No Perfect Randomized Composition — Draconitic Research

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∘ g) =Θ (1/(log 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.

An overlooked weakening of perfect normality: Perfect regularity in spaces and locales
Ana Belén Avilez, Guram Bezhanishvili, Joanne Walters-Wayland
arXiv7 Sep 2026PreprintarXiv licenceFull textAlgebra & number theory Analysis & PDEsarXiv
On special perfect polynomials over 𝔽₂
O. Rahavandrainy
arXiv17 Oct 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
Every commutative perfect ring is a quotient of an almost perfect domain
Xiaolei Zhang
arXiv18 Oct 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
ON ODD PERFECT NUMBERS
Theophilus Agama
HAL27 Sep 2026PreprintCC BY-ND 4.0Full textGeneral mathematicsHAL
ON THE DISTRIBUTION OF PERFECT NUMBERS AND RELATED SEQUENCES VIA THE NOTION OF THE DISK
T Agama
HAL27 Sep 2026PreprintCC BY-ND 4.0Full textGeneral mathematicsHAL

Cite

BibTeX RIS

BibTeX

@misc{meiburg2026perfect,
  title = {{No Perfect Randomized Composition}},
  author = {Alexander Meiburg},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.31638},
  eprint = {2610.31638},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.31638},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - No Perfect Randomized Composition
AU  - Alexander Meiburg
PY  - 2026
DA  - 2026/10/22
PB  - arXiv
DO  - 10.48550/arxiv.2610.31638
UR  - https://arxiv.org/abs/2610.31638
AB  - 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) =Θ (1/(log 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.
ER  -

Abstract

Related

Cite