Relative Discrepancy Does Not Separate Information and Communication Complexity

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=cpq_3Xdn6C0


Category:
Guide
Duration: 36:19
200 views
0

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



Other Videos By Simons Institute for the Theory of Computing


2015-04-27Lucky Talk: A Communication Game Approach to the Sensitivity Conjecture
2015-04-27Streaming Interactive Proofs and Arthur-Merlin Communication
2015-04-27Counting Distinct Elements in the Message Passing Model
2015-04-27Internal Compression of Protocols to Entropy
2015-04-27Tutorial on Coding for Interactive Communication: Introduction and Overview
2015-04-27Tutorial on Efficient Coding for Interactive Communication via List Decoding
2015-04-27Streaming Lower Bounds for Approximating MAX-CUT
2015-04-27Answering FAQs in CSPs, PGMs, Databases, Logic and Matrix Operations
2015-04-27Exponential Separation of Information and Communication
2015-04-27Small Value Parallel Repetition for General Games
2015-04-27Relative Discrepancy Does Not Separate Information and Communication Complexity
2015-04-27Information Complexity is Computable
2015-04-27On Parallelizing Streaming Algorithms
2015-04-27Combinatorial Proofs of Concentration Bounds
2015-04-27On Geometric Measures for Information Complexity
2015-04-27Tribes is Hard in the Message Passing Model
2015-04-27How to Compress Asymmetric Communication
2015-04-27Do Read Errors Matter for DNA Assembly?
2015-04-08Interactive Information: Applications and New Directions
2015-03-25Lucky Talk: An Algorithmic Characterization of a Class of Inequalities
2015-03-25Strong Data Processing Inequalities and Estimation with Constraints


Tags:
Simons Institute
UC Berkeley
computer science
theory of computing
Information Theory
Sophie Laplante