Lower bounds in communication complexity based on factorization norms.
Nati LinialAdi ShraibmanPublished in: STOC (2007)
Keyphrases
- lower bound
- worst case
- upper bound
- branch and bound
- optimal solution
- computational complexity
- upper and lower bounds
- singular value decomposition
- average case complexity
- vc dimension
- computational cost
- decision problems
- matrix factorization
- communication cost
- communication systems
- space complexity
- information sharing
- communication protocol
- multi agent systems