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

摘要

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 op and PSPACE op .