Polynomials, Quantum Query Complexity, and Grothendieck's Inequality.

Scott Aaronson Andris Ambainis Janis Iraids Martins Kokainis Juris Smotrovs

Published in: CoRR (2015)

Keyphrases

query complexity
data complexity
membership queries
exact learning
vc dimension
concept class
expressive power
query evaluation
resource consumption