Exponential separation of information and communication... 3/3

244 views · Published 25 February 2016 · 54:02 · Indexed 12 November 2026

Channel: Institut Henri Poincaré · 2016 · Science & Technology

Watch on YouTube

Exponential separation of information and communication, and how to prove lower bounds on disjointness, and the non-negative rank of matrices
By Anup Rao (University of Washington)
Abstract: We discuss how to prove lower bounds on the randomized communication complexity of disjointness, and outline some applications to proving lower bounds on linear programs, boolean circuit depth and data structures. We will also explain why the information cost of a protocol can be much smaller than that the communication complexity of protocols.

More from this channel