摘要：We consider the standard two-party communication model. The central problem
studied in this article is how much one can save in information complexity by allowing an
error of ε.
• For arbitrary functions, we obtain lower bounds and upper bounds indicating a gain
that is of order Ω(h(ε)) and O(h(
√
ε)), respectively. Here h denotes the binary entropy
function.
• We analyze the case of the two-bit AND function in detail to show that for this function
the gain is Θ(h(ε)). This answers a question of Braverman et al. (STOC’13).
• We obtain sharp bounds for the set disjointness function of order n. For the case of
the distributional error, we introduce a new protocol that achieves a gain of Θ(
p
h(ε))
provided that n is sufficiently large. We apply these results to answer another question
of Braverman et al. regarding the randomized communication complexity of the set
disjointness function.
关键词：communication complexity; information complexity
