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

39 42

On the Ultimate Limit of Two-Terminal Interactive Computing

By Prakash Ishwar

two-terminal interactive source coding

We approach two-terminal interactive computing via distributed source coding in information theory. We characterize the minimum rate (bits per sample) for asymptotically error free computation when there is no limit on the number of messages that can be exchanged. Here, the minimum rate is viewed as a functional of the joint source distribution. The functions to be computed at the two terminals can be different. The functional characterization leads to _exact_ analytic closed-form expressions for the minimum rates for computing any Boolean function of independent inputs at only one terminal and both terminals. It also leads to an alternating “concavification” algorithm for approximating the minimum rate for general functions and distributions. We conclude by discussing connections to amortized distributional communication complexity and some open problems. This is based on joint work with Nan Ma at Boston University.

Information about the video

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

94A29 Source coding

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