Communication Lower Bounds Via the Chromatic Number

DOI10.1007/978-3-540-77050-3_19zbMath1135.68431OpenAlexW1560454943MaRDI QIDQ5458837

D. Sivakumar, Ravi Kumar

Publication date: 24 April 2008

Published in: FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77050-3_19

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An information statistics approach to data stream and communication complexity
• Entropy and sorting.
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• Space lower bounds for distance approximation in the data stream model
• Two applications of information complexity
• Approximate graph coloring by semidefinite programming
• On the Shannon capacity of a graph
• Privacy, additional information and communication
• Communication Complexity of Simultaneous Messages
• Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy
• Communication Complexity

This page was built for publication: Communication Lower Bounds Via the Chromatic Number