Dag-like Communication and Its Applications.
Dmitry Sokolov · 2016
In 1990 Karchmer and Widgerson considered the following communication problem \(\mathtt {Bit}\): Alice and Bob know a function \(f: \{0, 1\}^n \rightarrow \{0, 1\}\), Alice receives a point \(x \in f^{-1}(1)\), Bob receives \(y \in f^{-1}(0)\), and their goal is to find a position i such that \(x_i e y_i\). Karchmer and Wigderson proved that the minimal size of a boolean formula for the function f equals the size of the smallest communication protocol for the \(\mathtt {Bit}\) relation. In this paper we consider a model of dag-like communication complexity (instead of classical one where protocols correspond to trees). We prove an analogue of Karchmer-Wigderson Theorem for this model and boolean circuits. We also consider a relation between this model and communication PLS games proposed by Razborov in 1995 and simplify the proof of Razborov’s analogue of Karchmer-Wigderson Theorem for PLS games.