Spring 2015

Information Complexity is Computable

Friday, April 24th, 2015 4:00 pm4:30 pm

Add to Calendar

The information complexity of a function f is the minimum amount of information Alice and Bob need to exchange to compute the function f. We provide an algorithm for approximating the information complexity  of an arbitrary function f to within any additive error epsilon>0. In the process, we give the first explicit upper bound on the rate of convergence of the information complexity of f when restricted to b-bit protocols to the (unrestricted) information complexity of f.

Joint work with Jon Schneider.