Property Testing Lower Bounds via Communication Complexity.

Eric Blais Joshua Brody Kevin Matulef

Published in: Electron. Colloquium Comput. Complex. (2011)

Keyphrases

lower bound
worst case
upper bound
computational complexity
complexity measures
computational cost
space complexity
data acquisition
branch and bound
lower and upper bounds
np hard
search space
training set
computer networks
error bounds
communication networks
vc dimension
objective function