All reports by Author Jon Schneider:

__
TR15-023
| 10th February 2015
__

Mark Braverman, Jon Schneider#### Information complexity is computable

Mark Braverman, Jon Schneider

The information complexity of a function $f$ is the minimum amount of information Alice and Bob need to exchange to compute the function $f$. In this paper we provide an algorithm for approximating the information complexity of an arbitrary function $f$ to within any additive error $\alpha>0$, thus resolving an ... more >>>