Publication details

Bronislava Brejova. Dva problemy z teorie komunikacnej zlozitosti (Two open problems in communication complexity). Master thesis, Comenius University, Bratislava, April 1999.
Preprint, 630Kb | BibTeX

Abstract

Communication complexity is an area of computational complexity that
studies simple communication models and uses obtained lower bounds to
obtain lower bounds in other models of computation. In this thesis we
study two open problems in the area of communication complexity. We
survey known results and develop new partial results concerning both
problems.

We first study the problem of the amortized communication complexity.
Here, the goal is to determine whether it is possible to save some
communication if we compute the answer for several inputs
simultaneously. We have shown that for most functions it is not
possible to save more than 4 bits. We have also constructed a function
with amortized communication complexity equal exactly its
communication complexity.

In the second part of the thesis we study the simultaneous protocols
for three input functions. This is a relatively new model with deep
connections to other areas of computational complexity. However no
methods for finding lower bounds of communication complexity in this
model are known. We give combinatorial characterization of
communication complexity in this model. However our characterization
is quite complex and does not directly yield methods for proving lower
bounds.