Collection Nexus Trimester - 2016 - Distributed Computation and Communication Theme
Organisateur(s)
Date(s)
19/05/2024
Exponential separation of information and communication, and how to prove lower bounds on disjointness, and the non-negative rank of matrices (1)
De Anup Rao
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.
