Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-166 | 5th November 2023 15:54

Patterned non-determinism in communication complexity


Authors: Dmytro Gavinsky
Publication: 12th November 2023 07:18
Downloads: 63


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.

ISSN 1433-8092 | Imprint