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

Andris Ambainis

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

Keyphrases

query complexity
data complexity
membership queries
exact learning
concept class
vc dimension
resource consumption
learning algorithm
database
relational databases
uniform distribution