k-forrelation optimally separates Quantum and classical query complexity.

Nikhil Bansal Makrand Sinha

Published in: STOC (2021)

Keyphrases

query complexity
membership queries
data complexity
concept class
databases
exact learning
database
database systems
upper bound
sample size
scheduling algorithm
learning theory