2016 - T1 - WS2 - Fundamental inequalities and lower bounds theme

Collection 2016 - T1 - WS2 - Fundamental inequalities and lower bounds theme

Organizer(s) Green Larsen, Kasper ; Hassibi, Babak ; Kerenidis, Iordanis ; Yeung, Raymond

Date(s) 15/02/2016 - 26/02/2016

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

00:00:00 / 00:00:00

4 51

Lower Bound Techniques for Multiparty Communication Complexity

In this talk we will discuss multiparty communication complexity in the k-site model, where we have k machines, each having a piece of data and they want to jointly compute some function defined on the union of the k data sets via communication. The communication is point-to-point, and the goal is to minimize the total communication between the k sites. This model captures all point-to-point distributed computational models. We will give an introduction of the new techniques developed in the last few years for proving communication lower bounds in the k-site model. We believe that these techniques will have a wide applicability.

Information about the video

Date of recording 15/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

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

52:00

published on February 25, 2016

Partition-Symmetrical Entropy Functions

By Qi Chen

48:43

published on February 25, 2016

Secret Sharing in Distributed Storage Systems

By Salim El Rouayheb

51:42

published on February 25, 2016

A Composition Theorem for Conical Juntas with Applications to Query and Communication Complexity

By Thathatchar S. Jayram

48:45

published on February 25, 2016

Lower Bound Techniques for Multiparty Communication Complexity

By Qin Zhang

50:09

published on February 25, 2016

A little advice can be very helpful

By Arkadev Chattopadhyay

44:10

published on February 25, 2016

Geometry of the entropy region 1/3

By László Csirmaz

45:56

published on February 25, 2016

Geometry of the entropy region 2/3

By László Csirmaz

38:01

published on February 25, 2016

Geometry of the entropy region 3/3

By László Csirmaz

52:31

published on February 25, 2016

Entropy inequalities and linear rank inequalities

By Randall Dougherty

53:23

published on February 25, 2016

Fundamental Inequalities and Capacity Upper Bounds

By Young Han Kim

50:27

published on February 25, 2016

From Pigeons to Fano, and beyond 1/3

By Suresh Venkatasubramanian

43:40

published on February 25, 2016

From Pigeons to Fano, and beyond 2/3

By Suresh Venkatasubramanian

50:11

published on February 25, 2016

From Pigeons to Fano, and beyond 3/3

By Suresh Venkatasubramanian

48:46

published on February 25, 2016

Rate Regions for Network Coding: Computation, Symmetry, and Hierarchy

By John Walsh

49:16

published on February 29, 2016

Distributed Extremization : Fundamental Limits and Practical Schemes

By John Walsh

44:59

published on February 29, 2016

Shannon's Information Measures and Markov Structures 1/3

By Raymond Yeung

51:01

published on February 29, 2016

Shannon's Information Measures and Markov Structures 2/3

By Raymond Yeung

31:34

published on February 29, 2016

Shannon's Information Measures and Markov Structures 3/3

By Raymond Yeung

52:44

published on February 29, 2016

Beyond Shannon EPI: a Completely Monotone Conjecture

By Fan Cheng

42:52

published on February 29, 2016

On Outer Bounds for the Storage-Repair-Bandwidth Tradeoff of Exact-Repair Regenerating Codes

By P. Vijay Kumar

50:39

published on February 29, 2016

Entropy region and convolution 1/3

By František Matúš

51:47

published on February 29, 2016

Entropy region and convolution 2/3

By František Matúš

38:33

published on February 29, 2016

Entropy region and convolution 3/3

By František Matúš

46:18

published on March 14, 2016

Ingleton-violating Points in the Entropy Region

By Nigel Boston

40:56

published on March 14, 2016

Data Structure Lower Bounds 1/3

By Kasper Green Larsen

35:33

published on March 14, 2016

Data Structure Lower Bounds 2/3

By Kasper Green Larsen

38:59

published on March 14, 2016

Data Structure Lower Bounds 3/3

By Kasper Green Larsen

46:01

published on March 14, 2016

Bounds on secure regenerating codes

By Kenneth Shum

55:06

published on March 14, 2016

Simple Algorithms and Guarantees for Low Rank Matrix Completion over GF(2)

By Babak Hassibi

42:28

published on March 14, 2016

Finite Dynamical Systems, Causal Networks and Information Inequalities - Part 1A

By Søren Riis

40:28

published on March 14, 2016

Finite Dynamical Systems, Causal Networks and Information Inequalities - Part 2A

By Søren Riis

35:43

published on March 14, 2016

Finite Dynamical Systems, Causal Networks and Information Inequalities - Part 2B

By Søren Riis

49:57

published on March 14, 2016

Coded MapReduce : how to optimally trade computation with communication

By Salman Avestimehr

51:36

published on March 14, 2016

Rectangle inequalities for data structure lower bounds

By Yitong Yin

39:59

published on March 14, 2016

Lower bounds for streaming problems 1/3

By Raphael Clifford

50:53

published on March 14, 2016

Lower bounds for streaming problems 2/3

By Raphael Clifford

40:38

published on March 14, 2016

Lower bounds for streaming problems 3/3

By Raphael Clifford

44:05

published on March 14, 2016

Dual Information Inequalities

By Tarik Kaced

36:27

published on March 14, 2016

Finding the fundamental limits of information systems: A computational approach

By Chao Tian

48:34

published on March 14, 2016

Aspects of Entropies and Inequalities 1/3

By Terence Chan

47:20

published on March 14, 2016

Aspects of Entropies and Inequalities 2/3

By Terence Chan

47:29

published on March 14, 2016

Aspects of Entropies and Inequalities 3/3

By Terence Chan

47:49

published on March 14, 2016

The Stam region, or the differential entropy region for sums of independent random vectors

By Mokshay Madiman

44:25

published on March 14, 2016

Abelian Group Representability and Fundamental Inequalities

By Frédérique Oggier

49:06

published on March 14, 2016

How to Approximate a Set without Knowing it's Size in Advance

By Udi Wieder

47:25

published on March 14, 2016

Branching Programs 1/3

By Paul Beame

57:40

published on March 14, 2016

Branching Programs 2/3

By Paul Beame

47:03

published on March 14, 2016

Branching Programs 3/3

By Paul Beame

45:26

published on March 14, 2016

Network Coding for Inter-cloud Storage

By Yuchong Hu

47:37

published on March 14, 2016

Tight Cell-probe bounds for Online Hamming distance

By Benjamin Sach

52:25

published on March 14, 2016

Advances in Characterizing Turnstile Streaming Algorithms as Linear Sketches

By David Woodruff

Copyright Carmin.tv 2025

Give feedback