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