Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR18-177 | 1st October 2018 07:19

The Diptych of Communication Complexity Classes in the Best-partition Model and the Fixed-partition Model

TR18-177
Authors: Alexander Knop
Publication: 29th October 2018 20:46
Keywords:

Abstract:

Most of the research in communication complexity theory is focused on the
fixed-partition model (in this model the partition of the input between
Alice and Bob is fixed). Nonetheless, the best-partition model (the model
that allows Alice and Bob to choose the partition) has a lot of
applications in studying stream algorithms and complexity of branching
programs.

In the paper, we show how to transform separations between communication
complexity classes from the fixed-partition to the best-partition models.
Using these and previously known methods, we give an answer to the open question
asked by Goos, Pitassi, and Watson by providing an almost complete
picture of the relations between best-communication complexity classes
between P$_{\mathrm{op}}$ and PSPACE$_{\mathrm{op}}$.

ISSN 1433-8092 | Imprint