Problem 77: Frontiers in Structural Communication Complexity

Suggested by	Justin Thaler
Source	Banff 2017
Short link	https://sublinear.info/77

In the $\mathbf{UPP}$ communication model, two parties execute a (private coin) randomized communication protocol, and must output the correct answer with probability strictly greater than 1/2. Forster [Forster-01] proved a linear lower bound on the $\mathbf{UPP}$ communication complexity of Inner Product Mod 2. $\mathbf{UPP}$ is essentially the most powerful two-party communication model against which we know how to prove lower bounds.

The (informal) open question is to prove a superlogarithmic lower bound for any natural communication complexity class that can compute problems outside of $\mathbf{UPP}$.

Here are two interesting candidate communication classes (both of these classes are subsets of $\mathbf{AM}$, a well-known frontier class in communication complexity).

1. The communication analog of non-interactive statistical zero knowledge proofs ($\mathbf{NISZK}$). This model can be defined as follows. For a given function $f(x, y) \to \{0, 1\}$, Alice and Bob engage in a (private coin) randomized communication protocol in which they exchange at most $k$ bits, at the end of which Bob outputs a string in $\{0, 1\}^k$. If $f(x, y)=1$ (respectively, $f(x, y)=0$), then the distribution of Bob's output string must have statistical distance at most $1/3$ (respectively, at least $2/3$) from uniform. The cost of the protocol is $k$.
2. The communication complexity class $\mathbf{OIP}_+^{[2]}$, which is the two-party communication analog of 2-message streaming interactive proofs [ChakrabartiCMTV-15]. This model involves three parties: Alice, Bob, and Merlin. Alice knows $x$, Bob knows $y$, and Merlin knows both $x$ and $y$. At the start of the protocol, Alice sends a randomized message to Bob (not seen by Merlin). Then Bob sends a message to Merlin, who sends a single message back to Bob. Bob then outputs 0 or 1. If $f(x, y)=1$, then there must be a Merlin strategy that convinces Bob to output 1 with probability at least 2/3. If $f(x, y)=0$, then for every Merlin strategy, Bob must output 0 with probability at least $2/3$. The cost of the protocol is the sum of the length of all three messages sent (Alice to Bob, Bob to Merlin, Merlin to Bob).

[BoulandCHTV-16] showed that both $\mathbf{NISZK}$ and $\mathbf{OIP}_+^{[2]}$ can, with logarithmic cost, compute (promise) problems outside of $\mathbf{UPP}$. So the open question is to exhibit an explicit function, such as Disjointness or Inner-Product-Mod-2, that cannot be computed by logarithmic cost $\mathbf{NISZK}$ or $\mathbf{OIP}_+^{[2]}$ protocols. As far as we know, this is open even for 1-way $\mathbf{NISZK}$, in which Alice sends a single message to Bob of length $k$, after which Bob outputs a string in $\{0, 1\}^k$ that must be either close or far from uniform depending on whether $f(x, y)=1$. (This model is also a special case of $\mathbf{OIP}_+^{[2]}$.) Even this model can, with logarithmic cost, compute functions outside $\mathbf{UPP}$, yet as far as we know it is possible that Index does not have a logarithmic cost protocol in this model.