Property Testing Lower Bounds via Communication Complexity.
Eric BlaisJoshua BrodyKevin MatulefPublished in: Comput. Complex. (2012)
Keyphrases
- lower bound
- upper bound
- worst case
- branch and bound
- complexity measures
- objective function
- information sharing
- average case complexity
- upper and lower bounds
- communication networks
- communication systems
- lower and upper bounds
- communication protocol
- quadratic assignment problem
- computational complexity
- sample complexity
- communication channels
- software testing
- decision problems
- similarity measure