Playlist: 43 videos Workshops

Information Theory in Complexity Theory and Combinatorics

Apr. 20 – Apr. 24, 2015

This workshop focuses on the applications of information theoretic techniques in communication complexity and combinatorics.

Communication complexity studies the communication needed to compute functions whose inputs are...

1:17:3

Tutorial on Coding for Interactive Communication: Introduction and Overview

Anup Rao, University of Washington
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/anup-rao-2015-04-20
Visit talk page
0:36:23

Exponential Separation of Information and Communication

Gillat Kol, Institute for Advanced Study, Princeton
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/gillat-kol-2015-04-20
Visit talk page
0:26:31

Small Value Parallel Repetition for General Games

Ankit Garg, Princeton University
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/ankit-garg-2015-04-20
Visit talk page
0:31:19

Answering FAQs in CSPs, PGMs, Databases, Logic and Matrix Operations

Atri Rudra, SUNY Buffalo
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/atri-rudra-2015-04-22
Visit talk page
0:30:8

Streaming Lower Bounds for Approximating MAX-CUT

Michael Kapralov, IBM T.J. Watson Research Center
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/michael-kapralov-2015-04-20
Visit talk page
0:29:28

Extended Formulations and Information Complexity

Ankur Moitra, Massachusetts Institute of Technology
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/ankur-moitra-2015-04-20
Visit talk page
0:33:9

Welfare Maximization with Limited Interaction: Information and Communication in Economics

Omri Weinstein, Princeton University
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/omri-weinstein-2015-04-20
Visit talk page
0:29:32

A New Look at Gallager's Bounds

Nati Linial, Hebrew University of Jerusalem
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/nati-linial-2015-04-20
Visit talk page
1:18:48

Tutorial on Efficient Coding for Interactive Communication via List Decoding

Bernhard Haeupler, Carnegie Mellon University
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/bernhard-haeupler-2015-04-21
Visit talk page
0:36:19

Relative Discrepancy Does Not Separate Information and Communication Complexity

Sophie Laplante, Université Paris Diderot
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/sophie-laplante-2015-04-21
Visit talk page