Communication Complexity and Applications
Videos from BIRS Workshop
Kasper Green Larsen, Aarhus University
Monday Aug 25, 2014 09:14 - 10:02
Communication Complexity and Data Structures
Omri Weinstein, Columbia University
Monday Aug 25, 2014 10:38 - 11:37
Interactive Information Complexity
David Woodruff, IBM
Monday Aug 25, 2014 14:53 - 15:59
Lower Bounds for Data Streams
Jelani Nelson, Harvard University
Monday Aug 25, 2014 16:26 - 17:02
Time lower bounds for nonadaptive turnstile streaming algorithms
Ankit Garg, Microsoft Research
Monday Aug 25, 2014 17:06 - 17:52
Small value parallel repetition for general games
Rotem Oshman, Princeton University
Tuesday Aug 26, 2014 09:18 - 10:28
The Role of Communication Complexity in Distributed Computing
Arkadev Chattopadhyay, Tata Institute of Fundamental Research
Tuesday Aug 26, 2014 10:49 - 11:58
The state-of-affairs in the Number-on-Forehead model
Frédéric Magniez, Univ Paris Diderot
Tuesday Aug 26, 2014 12:00 - 12:35
Unidirectional Input/Output Streaming Complexity of Reversal and Sorting
Kasper Green Larsen, Aarhus University
Tuesday Aug 26, 2014 15:06 - 15:58
Log-squared Lower Bounds for Dynamic Data Structures
Kasper Green Larsen, Aarhus University
Tuesday Aug 26, 2014 15:06 - 15:58
Log-squared Lower Bounds for Dynamic Data Structures
Venkatesan Guruswami, UC Berkeley
Tuesday Aug 26, 2014 19:52 - 20:32
Communication with Imperfectly Shared Randomness
Hartmut Klauck, Centre for Quantum Technologies
Wednesday Aug 27, 2014 09:13 - 10:20
Quantum Communication Complexity
Emanuele Viola, Northeastern University
Wednesday Aug 27, 2014 10:45 - 11:18
The communication complexity of group multiplication
Omri Weinstein, Columbia University
Wednesday Aug 27, 2014 11:28 - 12:04
An Interactive Information Odometer and Applications
Joshua Brody, Swarthmore College
Thursday Aug 28, 2014 09:15 - 10:26
Property Testing Lower Bounds via Communication Complexity
Amir Yehudayoff, Technion-IIT
Thursday Aug 28, 2014 10:53 - 11:54
Simplified lower bounds on the multiparty communication complexity of disjointness
Andrew McGregor, University of Massachusetts Amherst
Thursday Aug 28, 2014 11:57 - 12:22
A Simple, Surprising, Simultaneous Protocol for Graph Connectivity
Justin Thaler, Yahoo! Labs
Thursday Aug 28, 2014 13:39 - 14:14
Stream Computation and Arthur-Merlin Communication
Krzysztof Onak, IBM TJ Watson Research Center
Thursday Aug 28, 2014 14:56 - 15:29
Superlinear Lower Bounds for Multipass Graph Processing
Ankit Garg, Microsoft Research
Thursday Aug 28, 2014 15:37 - 16:41
Small value parallel repetition for general games, continued
Sudipto Guha, University of Pennsylvania
Thursday Aug 28, 2014 19:53 - 20:42
Linear Sketches and Graph Algorithms
Thomas Watson, University of Memphis
Friday Aug 29, 2014 09:21 - 10:10
Zero-Information Protocols and Unambiguity in Arthur–Merlin Communication
Arkadev Chattopadhyay, Tata Institute of Fundamental Research
Friday Aug 29, 2014 10:24 - 11:15
A little advice can be very helpful