Krzysztof Onak: Small adjustments

2017-04-28T02:05:10Z

Small adjustments

Blackc4: 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..."

2017-03-31T19:25:50Z

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..."

New page

{{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 Alice's and Bob's inputs are random variables $X$ and $Y$, respectively, external information complexity for two-player, zero-error protocols is defined as follows.
$$
\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 the following conjecture.
$$
\textrm{IC}^\text{ext}(F,0,\mu) = \lim_{n\rightarrow\infty} \frac{\overline{\textrm{CC}}(F^n,0,\mu^n)}{n}\,.
$$

<references />

@@ 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, zero-error protocols is defined as follows.
+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)\,.
@@ 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.
-Either prove or disprove the following conjecture.
+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}\,.

Open Problems:76 - Revision history

Krzysztof Onak: Small adjustments

Blackc4: 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..."