When Is Amplification Necessary for Composition in Randomized Query Complexity?

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

Published in: APPROX-RANDOM (2020)

Keyphrases

query complexity
data complexity
membership queries
exact learning
dnf formulas
machine learning
expressive power
concept class