Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > CONVERGENCE RATE:
Reports tagged with convergence rate:
TR15-023 | 10th February 2015
Mark Braverman, Jon Schneider

Information complexity is computable

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 >>>

ISSN 1433-8092 | Imprint