# Difference between revisions of "Open Problems:80"

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

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 /> |

## Revision as of 23:00, 31 March 2017

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 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})$ [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 [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)$?