Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity.
Jürgen ForsterMatthias KrauseSatyanarayana V. LokamRustam MubarakzjanovNiels SchmittHans Ulrich SimonPublished in: FSTTCS (2001)
Keyphrases
- computational complexity
- high computational complexity
- memory requirements
- decision problems
- special case
- low complexity
- np complete
- computational cost
- explanatory power
- complexity analysis
- computational efficiency
- worst case
- np hard
- communication systems
- complexity reduction
- linear complexity
- communication technologies
- space complexity
- semantic relations
- communication networks
- closed form
- computationally efficient
- case study
- information exchange
- communication channels
- data acquisition
- information sharing
- linear constraints
- resource constrained
- lower bound
- attribute values
- communication patterns
- least squares