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 \epsilon.
For arbitrary functions, we obtain lower bounds and upper bounds indicating a gain that is of order \Omega(h(\epsilon)) and O(h(\sqrt{\epsilon})). ... more >>>