"Amplification"

When Is Amplification Necessary for Composition in Randomized Query Complexity?

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

Shalev Ben-David, Mika Göös, Robin Kothari, Thomas Watson