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:32:15

Streaming Interactive Proofs and Arthur-Merlin Communication

Amit Chakrabarti, Dartmouth College
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/amit-chakrabarti-2015-04-23
Visit talk page
0:34:9

A Communication Game Approach to the Sensitivity Conjecture

Mike Saks, Rutgers University
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/mike-saks-2015-04-23
Visit talk page
0:31:53

Deterministic Communication vs. Partition Number

Toniann Pitassi, University of Toronto
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/toniann-pitassi-2015-04-24
Visit talk page
0:35:39

Interactive and Amortized Communication – An Information Theoretic Perspective

Alon Orlitsky, UC San Diego
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/alon-orlitsky-2015-04-23
Visit talk page
0:36:41

Lucky Talk: A Communication Game Approach to the Sensitivity Conjecture

Mike Saks, Rutgers University
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/lucky-talk-2
Visit talk page
0:25:40

Counting Distinct Elements in the Message Passing Model

David Woodruff, IBM Almaden
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/david-woodruff-2015-04-24
Visit talk page
0:34:41

Superlinear Lower Bounds for Multipass Graph Processing

Krzysztof Onak, IBM T.J. Watson Research Center
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/krzysztof-onak-2015-04-24
Visit talk page
0:34:12

Tribes is Hard in the Message Passing Model

Arkadev Chattopadhyay, Tata Institute of Fundamental Research
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/arkadev-chattopadhyay-2015-04-24
Visit talk page
0:31:31

Combinatorial Proofs of Concentration Bounds

Thomas Holenstein, ETH Zürich
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/thomas-holenstein-2015-04-24
Visit talk page
0:27:1

How to Compress Asymmetric Communication

Sivaramakrishnan Natarajan Ramamoorthy, University of Washington
Information Theory in Complexity Theory and Combinatorics
http://simons.berkeley.edu/talks/sivaramakrishnan-natarajan-ramamoorthy-2015-04-24
Visit talk page