When Is Amplification Necessary for Composition in Randomized Query Complexity?

Shalev Ben-David, Mika Göös, Robin Kothari +1

Suppose we have randomized decision trees for an outer function $f$ and an inner function $g$. The natural approach for obtaining a randomized decision tree for the composed functi…