Lower Bounds on the Randomized Communication Complexity of Read-Once Functions.
Nikos LeonardosMichael E. SaksPublished in: Computational Complexity Conference (2009)
Keyphrases
- optimal solution
- lower bound
- worst case
- upper bound
- branch and bound
- np hard
- objective function
- branch and bound algorithm
- max sat
- randomized algorithms
- complexity measures
- average case complexity
- computational cost
- communication networks
- lower bounding
- optimal cost
- computational complexity
- communication systems
- space complexity
- decision problems
- network flow
- communication overhead