Exponential separation of information and communication, and how to prove lower bounds on disjointness, and the non-negative rank of matrices (1) | Vidéo | Carmin.tv

00:00:00 / 00:00:00

Exponential separation of information and communication, and how to prove lower bounds on disjointness, and the non-negative rank of matrices (1)

Appears in collection : Nexus Trimester - 2016 - Distributed Computation and Communication Theme

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.

Information about the video

Date of recording 10/02/2016
Date of publication 25/02/2016
Institution IHP
Format MP4

Domain(s)

Computer Science

MSC codes

68P30 Coding and information theory

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow

Copyright Carmin.tv 2024

Give feedback