The Partition Bound for Classical Communication Complexity and Query Complexity

Rahul Jain Hartmut Klauck

Published in: CoRR (2009)

Keyphrases

query complexity
data complexity
membership queries
worst case
vc dimension
upper bound
concept class
lower bound
exact learning
computational complexity
knowledge representation
query answering
resource consumption