Spring 2017

Trading Information Complexity for Error

Monday, April 10th, 2017 3:30 pm4:00 pm

Add to Calendar

We consider the standard two-party communication model. The central problem studied in this talk is how much one can save in information complexity by allowing an error of epsilon. 
We answer a question of Braverman by establishing a gap between the two different notions of the prior-free information cost. This implies that amortized randomized communication complexity is not necessarily equal to the amortized distributional communication complexity with respect to the hardest distribution. 
This is based on a joint work with Yuval Dagan, Yuval Filmus, and Yaqiao Li.