Open Problems:77 - Revision history

Krzysztof Onak: Formatting

2017-04-28T02:41:02Z

Formatting

Krzysztof Onak: Formatting

2017-04-28T02:35:12Z

Formatting

2601:14F:4402:7A60:FD68:75C:63F5:E808 at 12:31, 4 April 2017

2017-04-04T12:31:03Z

JThaler at 16:17, 1 April 2017

2017-04-01T16:17:42Z

Blackc4: Created page with "{{Header |source=banff17 |who=Justin Thaler }} "

2017-03-31T19:55:41Z

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

New page

{{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>
+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}$.

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

@@ Line 16: / Line 16: @@
 {{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.
+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 />

← Older revision		Revision as of 16:17, 1 April 2017
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 />