Communication Complexity and Applications

Videos from BIRS Workshop

, Aarhus University
- 10:02
Communication Complexity and Data Structures
Watch video | Download video: 201408250914-Larsen.mp4 (137M)
, Columbia University
- 11:37
Interactive Information Complexity
Watch video | Download video: 201408251038-Weinstein.mp4 (177M)
, IBM
- 15:59
Lower Bounds for Data Streams
Watch video | Download video: 201408251453-Woodruff.mp4 (191M)
, Harvard University
- 17:02
Time lower bounds for nonadaptive turnstile streaming algorithms
Watch video | Download video: 201408251626-Nelson.mp4 (102M)
, Microsoft Research
- 17:52
Small value parallel repetition for general games
Watch video | Download video: 201408251706-Garg.mp4 (126M)
, Princeton University
- 10:28
The Role of Communication Complexity in Distributed Computing
Watch video | Download video: 201408260918-Oshman.mp4 (256M)
, Tata Institute of Fundamental Research
- 11:58
The state-of-affairs in the Number-on-Forehead model
Watch video | Download video: 201408261049-Chattopadhyay.mp4 (213M)
, Univ Paris Diderot
- 12:35
Unidirectional Input/Output Streaming Complexity of Reversal and Sorting
Watch video | Download video: 201408261200-Magniez.mp4 (93M)
, Aarhus University
- 15:58
Log-squared Lower Bounds for Dynamic Data Structures
Watch video | Download video: 201408261506-Larsen.mp4 (150M)
, Aarhus University
- 15:58
Log-squared Lower Bounds for Dynamic Data Structures
Watch video | Download video: 201408261506-Onak.mp4 (95M)
, UC Berkeley
- 20:32
Communication with Imperfectly Shared Randomness
Watch video | Download video: 201408261952-Guruswami.mp4 (108M)
, Centre for Quantum Technologies
- 10:20
Quantum Communication Complexity
Watch video | Download video: 201408270913-Klauck.mp4 (181M)
, Northeastern University
- 11:18
The communication complexity of group multiplication
Watch video | Download video: 201408271045-Viola.mp4 (118M)
, Columbia University
- 12:04
An Interactive Information Odometer and Applications
Watch video | Download video: 201408271128-Weinstein.mp4 (101M)
, Swarthmore College
- 10:26
Property Testing Lower Bounds via Communication Complexity
Watch video | Download video: 201408280915-Brody.mp4 (189M)
, Technion-IIT
- 11:54
Simplified lower bounds on the multiparty communication complexity of disjointness
Watch video | Download video: 201408281053-Yehudayoff.mp4 (262M)
, University of Massachusetts Amherst
- 12:22
A Simple, Surprising, Simultaneous Protocol for Graph Connectivity
Watch video | Download video: 201408281157-McGregor.mp4 (81M)
, Yahoo! Labs
- 14:14
Stream Computation and Arthur-Merlin Communication
Watch video | Download video: 201408281339-Thaler.mp4 (93M)
, IBM TJ Watson Research Center
- 15:29
Superlinear Lower Bounds for Multipass Graph Processing
Watch video | Download video: 201408281456-Onak.mp4 (95M)
, Microsoft Research
- 16:41
Small value parallel repetition for general games, continued
Watch video | Download video: 201408281537-Garg.mp4 (280M)
, University of Pennsylvania
- 20:42
Linear Sketches and Graph Algorithms
Watch video | Download video: 201408281953-Guha.mp4 (134M)
, University of Memphis
- 10:10
Zero-Information Protocols and Unambiguity in Arthur–Merlin Communication
Watch video | Download video: 201408290921-Watson.mp4 (120M)
, Tata Institute of Fundamental Research
- 11:15
A little advice can be very helpful
Watch video | Download video: 201408291024-Chattopadhyay.mp4 (134M)