Trading information complexity for error II: the case of a large error and external information complexity

Two problems are studied in this paper. (1) How much external or internal information cost is required to compute a Boolean-valued function with an error at most $1/2-ε$ for a small $ε$? It is shown that information cost of order $ε^2$ is necessary and of order $ε$ is sufficient. (2) How much external information cost can be saved to compute a function with a small error $ε>0$ comparing to the case when no error is allowed? It is shown that information cost of order at least $ε$ and at most $h(\sqrtε)$ can be saved. Except the $O(h(\sqrtε))$ upper bound, the other three bounds are tight. For distribution $μ$ that is equally distributed on $(0,0)$ and $(1,1)$, it is shown that $IC^{ext}_μ(XOR, ε)=1-2ε$ where XOR is the two-bit xor function. This equality seems to be the first example of exact information complexity when an error is allowed.