A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions.

Shalev Ben-David Eric Blais

Published in: CoRR (2020)

Keyphrases

query complexity
data complexity
membership queries
lower bound
worst case
upper bound
exact learning
decision trees
concept class
dnf formulas
machine learning
learning algorithm
query language
image compression
resource consumption