The Partition Bound for Classical Communication Complexity and Query Complexity.

Rahul Jain Hartmut Klauck

Published in: Computational Complexity Conference (2010)

Keyphrases

query complexity
data complexity
worst case
upper bound
membership queries
lower bound
vc dimension
concept class
exact learning
dnf formulas