Separations in query complexity using cheat sheets.

Scott Aaronson Shalev Ben-David Robin Kothari

Published in: STOC (2016)

Keyphrases

query complexity
data complexity
membership queries
exact learning
concept class
resource consumption
upper bound
query answering
database
objective function
vc dimension