Monte Carlo to Las Vegas for Recursively Composed Functions

Bandar Al-Dhalaan, Shalev Ben-David

For a (possibly partial) Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ as well as a query complexity measure $M$ which maps Boolean functions to real numbers, define the compositio…