Open Problems:77

2017-04-04T12:31:03Z

2601:14F:4402:7A60:FD68:75C:63F5:E808:

{{Header
|source=banff17
|who=Justin Thaler
}}

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 {{cite|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.<ref> Let us ignore the example of Parity-P, which can compute Inner Product Mod 2 with constant communication, yet a linear lower bound on the Parity-P communication complexity of Equality follows from a matrix rank argument.</ref>

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).

a) 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$.

b) The communication complexity class $\mathbf{OIP}_+^{[2]}$, which is the two-party communication analog of 2-message streaming interactive proofs {{cite|ChakrabartiCMTV-15}}. This model involves 3 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).

{{cite|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.

==Notes==
<references />

Open Problems in Sublinear Algorithms - User contributions [en]

Open Problems:77