Communication Complexity and Sequential Compuation

Abstract The communication complexity of two-party protocols introduced by Abelson and Yao is one of the most intensively studied complexity measures for computing problems. This is a consequence of the relation of communication complexity to many fundamental (mainly parallel) complexity measures. This paper focuses on the relation between communication complexity and the following three complexity measures of sequential computation: the size of finite automata, the time- and space-complexity measures of Turing machines and the time- and space-complexity for data structure problems. We present a survey of the known relations between communication complexity and these three problem areas and formulate several open problems for further research.

Authors

• Juraj Hromkovic
• Georg Schnitger

Keywords

No keywords are indexed for this paper.