Patterned non-determinism in communication complexity

Dmytro Gavinsky

We define and study the model of patterned non-determinism in bipartite communication complexity, denoted by $PN{P}^{X\leftrightarrow Y}$. It generalises the known models $UP^{X\left…