__
TR23-166 | 5th November 2023 15:54
__

#### Patterned non-determinism in communication complexity

**Abstract:**
We define and study the model of patterned non-determinism in bipartite communication complexity, denoted by $PNP^{X\leftrightarrow Y}$.

It generalises the known models $UP^{X\leftrightarrow Y}$ and $FewP^{X\leftrightarrow Y}$ through relaxing the constraints on the witnessing structure of the underlying $NP^{X\leftrightarrow Y}$-protocol.

It is shown that for the case of total functions $PNP^{X\leftrightarrow Y}$ equals $P^{X\leftrightarrow Y}$ (similarly to $UP^{X\leftrightarrow Y}$ and $FewP^{X\leftrightarrow Y}$).

Moreover, the corresponding exhaustive witness-searching problem -- determining the full set of witnesses that lead to the acceptance of a given input pair -- also has an efficient deterministic protocol.

The possibility of efficient exhaustive $PNP^{X\leftrightarrow Y}$-search is used to analyse certain three-party communication regime (under the "number in hand" input partition):

The corresponding three-party model is shown to be as strong qualitatively as the weakest among its two-party amplifications obtained by allowing free communication between a pair of players.