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
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
-
29:47
10 ans du Groupe Calcul : Histoire du Calcul - Introduction
-
52:14
Gauss, Jacobi, Seidel, Richardson, Krylov: the Invention of Iterative Methods
-
55:33
Les "invariants arithmétiques" de H. Poincaré
-
1:08:53
Henri Poincaré, a founding father of the modern theory of PDEs
-
57:13
Sympletic topology from Poincaré to Gromov
-
57:35
Structural Realism, Then and Now
-
46:26
Poincaré inequalities in probability and geometric analysis
-
1:02:05
On the contributions of Henri Poincaré to modern geophysics...