We define and study the model of patterned non-determinism in bipartite communication complexity, denoted by PNPX↔Y. It generalises the known models UPX↔Y and FewPX↔Y through relaxing the constraints on the witnessing structure of the underlying NPX↔Y -protocol.
It is shown that for the case of total functions PNPX↔Y equals PX↔Y (similarly to UPX↔Y and FewPX↔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.
Structurally, the possibility of efficient exhaustive PNPX↔Y -search summarises the above results and can be stated like this: if f1, . . . . ,fm are bipartite total Boolean functions with efficient deterministic protocols, then for every input (x, y) the set {i|fi (x, y) = ⊤} can be found by a deterministic protocol of cost poly-logarithmic in n and the total number of such sets for these fi’s.
Finally, the possibility of efficient exhaustive PNPX↔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.