ECCC-Report TR23-166https://eccc.weizmann.ac.il/report/2023/166Comments and Revisions published for TR23-166en-usSun, 12 Nov 2023 07:18:52 +0200
Paper TR23-166
| Patterned non-determinism in communication complexity |
Dmytro Gavinsky
https://eccc.weizmann.ac.il/report/2023/166We 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.Sun, 12 Nov 2023 07:18:52 +0200https://eccc.weizmann.ac.il/report/2023/166