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...") 
(No difference)

Revision as of 19:25, 31 March 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, external information complexity for twoplayer, zeroerror 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 zeroerror 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}\,. $$