Separations in Query Complexity Based on Pointer Functions.

Andris Ambainis Kaspars Balodis Aleksandrs Belovs Troy Lee Miklos Santha Juris Smotrovs

Published in: CoRR (2015)

Keyphrases

query complexity
data complexity
membership queries
machine learning
data structure
databases
lower bound
domain knowledge
expressive power
concept class