Separations in query complexity using cheat sheets.

Scott Aaronson Shalev Ben-David Robin Kothari

Published in: Electron. Colloquium Comput. Complex. (2015)

Keyphrases

query complexity
data complexity
membership queries
exact learning
expressive power
data sources
vc dimension
dnf formulas