Difference between revisions of "Open Problems:80"
(Changed to the correct definition of MA model that states to ensure communication cost *includes* the proof size.) |
|||
| (3 intermediate revisions by 2 users not shown) | |||
| Line 3: | Line 3: | ||
|who=Amit Chakrabarti | |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$, | |
| − | We have a function $f:\mathcal{X}\times\mathcal{Y}\rightarrow\{0,1\}$. In the | ||
* $f(x,y) = 1 \implies \exists \text{ proof}: \Pr[\Pi(x,y,\text{ proof})=1] \ge 2/3$, and | * $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$. | * $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 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})$. | ||
| − | + | 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). | |
| − | |||
| − | |||
| − | |||
| − | For $x,y\in\{0,1\}^{\binom{n}{2}}$, interpreting $x$ and $y$ as edges of an $n$ vertex graph, define $\ | ||
| − | Is $\textrm{MA}^\rightarrow(\ | + | Is $\textrm{MA}^\rightarrow(\mathbf{Connect}) = o(n)$? |
| − | |||
Latest revision as of 16:34, 26 January 2019
| Suggested by | Amit Chakrabarti |
|---|---|
| Source | Banff 2017 |
| Short link | https://sublinear.info/80 |
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)$. The communication cost here includes the proof size. It is known that $\textrm{MA}^\rightarrow(\mathbf{Disj}) = \tilde{O}(\sqrt{n})$ [AaronsonW-09] and $\textrm{MA}^\rightarrow(\mathbf{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 $\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 [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(\mathbf{Connect}) = o(n)$?
