Open Problems:80 - Revision history

2601:84:8800:8F56:EDEF:4FE1:4DAC:D316: Changed to the correct definition of MA model that states to ensure communication cost includes the proof size.

2019-01-26T16:34:58Z

Changed to the correct definition of MA model that states to ensure communication cost *includes* the proof size.

Krzysztof Onak: Formatting

2017-04-28T03:44:16Z

Formatting

Blackc4 at 22:50, 1 April 2017

2017-04-01T22:50:22Z

Blackc4 at 22:11, 1 April 2017

2017-04-01T22:11:54Z

Blackc4 at 23:00, 31 March 2017

2017-03-31T23:00:40Z

Blackc4: Created page with "{{Header |source=banff17 |who=Amit Chakrabarti }} "

2017-03-31T20:20:02Z

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

New page

{{Header
|source=banff17
|who=Amit Chakrabarti
}}

<references />

@@ Line 6: / Line 6: @@
 * $f(x,y) = 1 \implies \exists \text{ proof}: \Pr[\Pi(x,y,\text{ proof})=1] \ge 2/3$, and
 * $f(x,y) = 0 \implies \forall \text{ proofs}: \Pr[\Pi(x,y,\text{ proof})=1] \le 1/3$.
-We denote the communication complexity of $f$ in the above model as $\textrm{MA}^\rightarrow(f)$. The communication cost here does not include the proof size.
+We denote the communication complexity of $f$ in the above model as $\textrm{MA}^\rightarrow(f)$. The communication cost here includes the proof size.
 It is known that $\textrm{MA}^\rightarrow(\mathbf{Disj}) = \tilde{O}(\sqrt{n})$ {{cite|AaronsonW-09}} and $\textrm{MA}^\rightarrow(\mathbf{InnerProd}) = \tilde{O}(\sqrt{n})$.

@@ Line 3: / Line 3: @@
 |who=Amit Chakrabarti
 }}
+We have a function $f:\mathcal{X}\times\mathcal{Y}\rightarrow\{0,1\}$.  In the Merlin–Arthur communication model, Alice gets an $x\in\mathcal{X}$ and Bob gets a $y\in\mathcal{Y}$.  Merlin is an all-knowing, all-powerful entity who sends them a proof at the beginning.  Then Alice and Bob communicate to find $f(x,y)$.  A protocol $\Pi$ solves $f$ if, for all $x,y$,
 * $f(x,y) = 1 \implies \exists \text{ proof}: \Pr[\Pi(x,y,\text{ proof})=1] \ge 2/3$, and
 * $f(x,y) = 0 \implies \forall \text{ proofs}: \Pr[\Pi(x,y,\text{ proof})=1] \le 1/3$.
-We denote the communication complexity of $f$ in the above model as $\textrm{MA}^\rightarrow(f)$.  Communication cost here does not include the proof size.
+For $x,y\in\{0,1\}^{\binom{n}{2}}$, interpreting $x$ and $y$ as edges of an $n$ vertex graph, define $\mathbf{Connect}$ as follows. If $x\cup y$ is connected, $\mathbf{Connect}(x,y) = 1$, else $\mathbf{Connect}(x,y)=0$.  Using the Ahn-Guha-McGregor {{cite|AhnGM-12}} linear sketch for connectivity, we can show that $D^\rightarrow(\mathbf{Connect}) = \tilde{O}(n)$, where $D^\rightarrow$ denotes one-way communication complexity (Alice sends one message to Bob, and there is no Merlin).
-Is $\textrm{MA}^\rightarrow(\textrm{is-conn}) = o(n)$?
+Is $\textrm{MA}^\rightarrow(\mathbf{Connect}) = o(n)$?

@@ Line 10: / Line 10: @@
 We denote the communication complexity of $f$ in the above model as $\textrm{MA}^\rightarrow(f)$.  Communication cost here does not include the proof size.
-It is known that $\textrm{MA}^\rightarrow(\textrm{DISJ}) = \tilde{O}(\sqrt{n})$ {{cite|Aaronson-Wigderson-XX}} and $\textrm{MA}^\rightarrow(\textrm{InnerProd}) = \tilde{O}(\sqrt{n})$.
+It is known that $\textrm{MA}^\rightarrow(\textrm{DISJ}) = \tilde{O}(\sqrt{n})$ {{cite|AaronsonW-09}} and $\textrm{MA}^\rightarrow(\textrm{InnerProd}) = \tilde{O}(\sqrt{n})$.
-For $x,y\in\{0,1\}^{\binom{n}{2}}$, interpreting $x$ and $y$ as edges of an $n$ vertex graph, define $\textrm{is-conn}$ as follows. If $x\cup y$ is connected, $\textrm{is-conn}(x,y) = 1$, else $\textrm{is-conn}(x,y)=0$.  Using the Ahn-Guha-McGregor {{cite|AhnGM-XX}} linear sketch for connectivity, we can show that $D^\rightarrow(\textrm{is-conn}) = \tilde{O}(n)$, where $D^\rightarrow$ denotes one-way communication complexity (Alice sends one message to Bob, and there is no Merlin).
+For $x,y\in\{0,1\}^{\binom{n}{2}}$, interpreting $x$ and $y$ as edges of an $n$ vertex graph, define $\textrm{is-conn}$ as follows. If $x\cup y$ is connected, $\textrm{is-conn}(x,y) = 1$, else $\textrm{is-conn}(x,y)=0$.  Using the Ahn-Guha-McGregor {{cite|AhnGM-12}} linear sketch for connectivity, we can show that $D^\rightarrow(\textrm{is-conn}) = \tilde{O}(n)$, where $D^\rightarrow$ denotes one-way communication complexity (Alice sends one message to Bob, and there is no Merlin).
 Is $\textrm{MA}^\rightarrow(\textrm{is-conn}) = o(n)$?
 <references />

@@ Line 12: / Line 12: @@
 It is known that $\textrm{MA}^\rightarrow(\textrm{DISJ}) = \tilde{O}(\sqrt{n})$ {{cite|Aaronson-Wigderson-XX}} and $\textrm{MA}^\rightarrow(\textrm{InnerProd}) = \tilde{O}(\sqrt{n})$.
-For $x,y\in\{0,1\}^{\binom{n}{2}}$, interpreting $x$ and $y$ as edges of an $n$ vertex graph, define $\textrm{is-conn}$ as follows. If $x\cup y$ is connected, $\textrm{is-conn}(x,y) = 1$, else $\textrm{is-conn}(x,y)=0$.  Using the Ahn-Guha-McGregor {{cite|AhnGM-XX}} linear sketch for connectivity, we can show that $D^\rightarrow(\textrm{is-conn}) = \tilde{O}(n)$, where $D^\rightarrow$ denotes one-way communication complexity (Alice sends once message to Bob, and there is no Merlin).
+For $x,y\in\{0,1\}^{\binom{n}{2}}$, interpreting $x$ and $y$ as edges of an $n$ vertex graph, define $\textrm{is-conn}$ as follows. If $x\cup y$ is connected, $\textrm{is-conn}(x,y) = 1$, else $\textrm{is-conn}(x,y)=0$.  Using the Ahn-Guha-McGregor {{cite|AhnGM-XX}} linear sketch for connectivity, we can show that $D^\rightarrow(\textrm{is-conn}) = \tilde{O}(n)$, where $D^\rightarrow$ denotes one-way communication complexity (Alice sends one message to Bob, and there is no Merlin).
 Is $\textrm{MA}^\rightarrow(\textrm{is-conn}) = o(n)$?
 <references />

← Older revision		Revision as of 23:00, 31 March 2017
Line 4:		Line 4:
	}}		}}

		+	We have a function $f:\mathcal{X}\times\mathcal{Y}\rightarrow\{0,1\}$. In the Merlin Arthur Communication model, Alice gets an $x\in\mathcal{X}$ and Bob gets a $y\in\mathcal{Y}$. Merlin is all-knowing, all-powerful entity who sends them a proof at the beginning. Then Alice and Bob communicate to find $f(x,y)$. A protocol $\Pi$ solves $f$ if, for all $x,y$,
		+	* $f(x,y) = 1 \implies \exists \text{ proof}: \Pr[\Pi(x,y,\text{ proof})=1] \ge 2/3$, and
		+	* $f(x,y) = 0 \implies \forall \text{ proofs}: \Pr[\Pi(x,y,\text{ proof})=1] \le 1/3$.

		+	We denote the communication complexity of $f$ in the above model as $\textrm{MA}^\rightarrow(f)$. Communication cost here does not include the proof size.

		+	It is known that $\textrm{MA}^\rightarrow(\textrm{DISJ}) = \tilde{O}(\sqrt{n})$ {{cite\|Aaronson-Wigderson-XX}} and $\textrm{MA}^\rightarrow(\textrm{InnerProd}) = \tilde{O}(\sqrt{n})$.
		+
		+	For $x,y\in\{0,1\}^{\binom{n}{2}}$, interpreting $x$ and $y$ as edges of an $n$ vertex graph, define $\textrm{is-conn}$ as follows. If $x\cup y$ is connected, $\textrm{is-conn}(x,y) = 1$, else $\textrm{is-conn}(x,y)=0$. Using the Ahn-Guha-McGregor {{cite\|AhnGM-XX}} linear sketch for connectivity, we can show that $D^\rightarrow(\textrm{is-conn}) = \tilde{O}(n)$, where $D^\rightarrow$ denotes one-way communication complexity (Alice sends once message to Bob, and there is no Merlin).
		+
		+	Is $\textrm{MA}^\rightarrow(\textrm{is-conn}) = o(n)$?
	<references />		<references />