# Difference between revisions of "Open Problems:77"

(Created page with "{{Header |source=banff17 |who=Justin Thaler }} <references />") |
|||

Line 4: | Line 4: | ||

}} | }} | ||

+ | 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$. 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 /> | <references /> |

## Revision as of 16:17, 1 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).

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

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