A quadratically tight partition bound for classical communication complexity and query complexity.

Rahul Jain Troy Lee Nisheeth K. Vishnoi

Published in: CoRR (2014)

Keyphrases

query complexity
worst case
lower bound
upper bound
data complexity
vc dimension
membership queries
concept class
exact learning
expressive power
databases
sample size
np complete
np hard
active learning
resource consumption
computational complexity
machine learning
dnf formulas
database