# Difference between revisions of "Open Problems:77"

(Formatting) |
|||

Line 10: | Line 10: | ||

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

− | + | # 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$. | |

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

− | + | {{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. | |

− | {{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]}$) | ||

==Notes== | ==Notes== | ||

<references /> | <references /> |

## Revision as of 02:35, 28 April 2017

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.^{[1]}

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

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

## Notes

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