Patterned non-determinism in communication complexity

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