2016 - T1 - WS1 - Distributed computation and communication theme

Collection 2016 - T1 - WS1 - Distributed computation and communication theme

Organizer(s) Gács, Péter ; Körner, János ; Schulman, Leonard

Date(s) 01/02/2016 - 12/02/2016

linked URL https://web.archive.org/web/20221228152145/http://iss.bu.edu/bobak/csnexus//distcomp.html

00:00:00 / 00:00:00

18 42

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

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 05/02/2016
Date of publication 25/02/2016
Institution IHP
Licence CC BY-NC-ND
Language English
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

All the collection videos

58:00

published on February 2, 2016

Recent Advances in Randomized Rumor Spreading

By George Giakkoupis

01:02:20

published on February 1, 2016

Different versions of Kolmogorov complexity and a priori probability: a gentle introduction (1/2)

By Alexander Shen

51:36

published on February 1, 2016

Different versions of Kolmogorov complexity and a priori probability: a gentle introduction (2/2)

By Alexander Shen

50:40

published on February 3, 2016

Relation between monotonic complexity and algorithmic probability (1/2)

By Péter Gács

51:31

published on February 25, 2016

Relation between monotonic complexity and algorithmic probability (2/2)

By Péter Gács

58:10

published on February 2, 2016

Knowledge and Coordinated Action (1/2)

By Yoram Moses

56:17

published on February 3, 2016

Knowledge and Coordinated Action (2/2) Coordination and Time

By Yoram Moses

56:14

published on February 2, 2016

On Parallels Between Shannon’s and Kolmogorov’s Information Theories (where the parallelism fails and why)

By Andrei Romashchenko

01:01:54

published on February 3, 2016

Distributed compression: the algorithmic-information-theoretical view

By Marius Zimand

46:30

published on February 25, 2016

Tensorization of information functionals (1/2) Forward and Reverse hypercontractivity using information measures

By Chandra Nair

51:22

published on February 25, 2016

Tensorization of information functionals (2/2) Applications in establishing optimality of Gaussian distributions and in a Boolean function Conjecture

By Chandra Nair

51:26

published on February 25, 2016

Communication Cost in Parallel Query Processing

By Dan Suciu

01:06:49

published on February 25, 2016

Information Theory: A Classical, Partial View

By Cédric Villani

55:41

published on February 25, 2016

Some Some Information-Theoretic Problems in Theoretical Computer Science - Part II

By Omri Weinstein

48:45

published on February 25, 2016

High Probability Guarantees in Repeated Games: Theory and Applications in Information Theory

By Amin Aminzadeh Gohari

50:40

published on February 25, 2016

Lower Bounds for Distributed Graph Problems via Information Theory

By Stephan Sebastian Holzer

55:23

published on February 25, 2016

Codes in graphs

By János Körner

55:16

published on February 25, 2016

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

By Anup Rao

56:46

published on February 25, 2016

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

By Anup Rao

54:02

published on February 25, 2016

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

By Anup Rao

46:55

published on February 25, 2016

Interactive Coding for Interactive Proofs

By Allison Bishop

53:42

published on February 25, 2016

A reductionist view of network information theory

By Michael Langberg

49:36

published on February 25, 2016

Interactive Information Complexity and Applications : Interactive Compression - Part I/1

By Omri Weinstein

01:12:42

published on February 25, 2016

Interactive Information Complexity and Applications : Interactive Compression - Part I/2

By Omri Weinstein

56:45

published on February 25, 2016

Interactive Information Complexity and Applications : Interactive Compression - Part II

By Omri Weinstein

55:42

published on February 25, 2016

Coding for interactive communication

By Ran Gelles

51:37

published on February 25, 2016

Tree codes - relaxations, constructions and applications

By Ran Gelles

55:08

published on February 25, 2016

Communication with Contextual Uncertainty

By Badih Ghazi

43:33

published on February 25, 2016

Secure and Reliable Codes for Cooperative Data Exchange

By Alex Sprintson

50:56

published on February 25, 2016

An Interactive Information Odometer and Applications

By Omri Weinstein

53:30

published on February 25, 2016

Strong Data Processing and the Entropy Power Inequality

By Thomas Courtade

52:06

published on February 25, 2016

Colony or ant, whose in charge?

By Ofer Feinerman

55:02

published on February 29, 2016

Polynomial-time interactive coding (1/2)

By Yael Kalai

48:20

published on February 25, 2016

Polynomial-time interactive coding (2/2)

By Yael Kalai

42:00

published on February 25, 2016

Confidence sharing: an economic strategy for efficient information flows in animal groups

By Amos Korman

57:06

published on April 14, 2016

Topology matters in communication

By Arkadev Chattopadhyay

52:43

published on February 25, 2016

Lower bounds for coding for multiparty interactive communication (1/2)

By Klim Efremenko

49:29

published on February 25, 2016

Lower bounds for coding for multiparty interactive communication (2/2)

By Klim Efremenko

58:20

published on February 25, 2016

On the Ultimate Limit of Two-Terminal Interactive Computing

By Prakash Ishwar

53:23

published on February 25, 2016

Worst-Case Optimal Algorithms for Parallel Query Processing

By Paris Koutris

01:01:54

published on February 25, 2016

Prospects for tree codes

By Dusa McDuff , Leonard Schulman

45:18

published on February 25, 2016

Randomized proof-labeling schemes

By Boaz Patt-Shamir

Copyright Carmin.tv 2025

Give feedback