Class Description

ZAMcc: Zero-Information Arthur-Merlin Communication Complexity

Similar to AMcc except that on each yes-input, the distribution of Merlin’s proof must leak no information about the input and moreover, this proof must be unique for each outcome of Arthur’s (i.e., Alice's and Bob's) randomness.

Contained in coNPcc [GPW16a].

Unlike with other communication complexity classes, it is not known whether every function can be computed with O(n) communication in the ZAMcc model. In fact it is not even obvious that every function can be computed at all in this model, but this turns out to be the case; indeed, there is an O(2n) upper bound for every function [GPW16a].

Closely related to "private simultaneous messages" protocols in cryptography [AR16].

Linked From

No class.