Distribution Testing Lower Bounds via Reductions from Communication Complexity.
Eric BlaisClément L. CanonneTom GurPublished in: Computational Complexity Conference (2017)
Keyphrases
- lower bound
- worst case
- upper bound
- objective function
- complexity measures
- branch and bound algorithm
- average case complexity
- communication protocol
- upper and lower bounds
- data distribution
- test set
- np hard
- computational complexity
- test cases
- decision problems
- spatial distribution
- lower and upper bounds
- software testing
- max sat
- special case
- neural network