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...

0:30:34

Non-Signalling Parallel Repetition Using de Finetti Reductions

Thomas Vidick, California Institute of Technology
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/thomas-vidick-2015-04-22
Visit talk page
0:31:52

Limits to Efficient Preprocessing

Andrew Drucker, University of Chicago
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/andrew-drucker-2015-04-22
Visit talk page
0:28:59

Parallel Repetition for Entangled Games via Fast Quantum Search

Henry Yuen, Massachusetts Institute of Technology
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/henry-yuen-2015-04-22
Visit talk page
0:34:31

Do Read Errors Matter for DNA Assembly?

Thomas Courtade, UC Berkeley
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/thomas-courtade-2015-04-22
Visit talk page
,
0:38:14

Tutorial on List Decodable Coding Schemes and Interactive Communication in Networks

Klim Efremenko, Tel Aviv University
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/klim-efremenko-ran-gelles-2015-04-23
Visit talk page
,
0:43:57

Tutorial on List Decodable Coding Schemes and Interactive Communication in Networks

Ran Gelles, Princeton University
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/klim-efremenko-ran-gelles-2015-04-23
Visit talk page
0:32:50

Information Theory and Polyhedral Combinatorics

Sebastian Pokutta, Georgia Institute of Technology
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/sebastian-pokutta-2015-04-23
Visit talk page
0:30:54

Information Theory and Additive Combinatorics

Mokshay Madiman, University of Delaware
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/mokshay-madiman-2015-04-23
Visit talk page
0:32:4

Lucky Talk: An Information Theoretic View of Hypercontractivity

Ehud Friedgut, Weizmann Institute
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/lucky-talk-1
Visit talk page
0:24:58

On Parallelizing Streaming Algorithms

Makrand Sinha, University of Washington
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/makrand-sinha-2015-04-23
Visit talk page