Difference between revisions of "Open Problems:76"
(Created page with "{{Header |source=banff17 |who=Mark Braverman }} For a function $F:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$, distribution $\mu$ on inputs $\{0,1\}^n\times\{0,1\}^n$, where...") |
m (Small adjustments) |
||
| Line 4: | Line 4: | ||
}} | }} | ||
| − | For a function $F:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$, distribution $\mu$ on inputs $\{0,1\}^n\times\{0,1\}^n$, where Alice's and Bob's inputs are random variables $X$ and $Y$, respectively, external information complexity for two-player | + | For a function $F:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$, distribution $\mu$ on inputs $\{0,1\}^n\times\{0,1\}^n$, where Alice's and Bob's inputs are random variables $X$ and $Y$, respectively, the external information complexity for two-player zero-error protocols is defined as |
$$ | $$ | ||
\textrm{IC}^\text{ext}(F,0,\mu) := \inf_{\Pi \text{ that solve $F$ correctly always}} I_\mu(\Pi;XY)\,. | \textrm{IC}^\text{ext}(F,0,\mu) := \inf_{\Pi \text{ that solve $F$ correctly always}} I_\mu(\Pi;XY)\,. | ||
| Line 10: | Line 10: | ||
We denote by $\overline{\textrm{CC}}(F^n,0,\mu^n)$ the expected communication complexity of $F^n$ with respect to the distribution $\mu^n$ for zero-error protocols. | We denote by $\overline{\textrm{CC}}(F^n,0,\mu^n)$ the expected communication complexity of $F^n$ with respect to the distribution $\mu^n$ for zero-error protocols. | ||
| − | Either prove or disprove | + | Either prove or disprove that |
$$ | $$ | ||
\textrm{IC}^\text{ext}(F,0,\mu) = \lim_{n\rightarrow\infty} \frac{\overline{\textrm{CC}}(F^n,0,\mu^n)}{n}\,. | \textrm{IC}^\text{ext}(F,0,\mu) = \lim_{n\rightarrow\infty} \frac{\overline{\textrm{CC}}(F^n,0,\mu^n)}{n}\,. | ||
Latest revision as of 02:05, 28 April 2017
| Suggested by | Mark Braverman |
|---|---|
| Source | Banff 2017 |
| Short link | https://sublinear.info/76 |
For a function $F:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$, distribution $\mu$ on inputs $\{0,1\}^n\times\{0,1\}^n$, where Alice's and Bob's inputs are random variables $X$ and $Y$, respectively, the external information complexity for two-player zero-error protocols is defined as $$ \textrm{IC}^\text{ext}(F,0,\mu) := \inf_{\Pi \text{ that solve $F$ correctly always}} I_\mu(\Pi;XY)\,. $$ We denote by $\overline{\textrm{CC}}(F^n,0,\mu^n)$ the expected communication complexity of $F^n$ with respect to the distribution $\mu^n$ for zero-error protocols.
Either prove or disprove that $$ \textrm{IC}^\text{ext}(F,0,\mu) = \lim_{n\rightarrow\infty} \frac{\overline{\textrm{CC}}(F^n,0,\mu^n)}{n}\,. $$
