Communication Complexity and Applications, II
Videos from BIRS Workshop
Rahul Jain, National University of Singapore
Monday Mar 20, 2017 09:16 - 10:14
Direct product theorems in communication
Jelani Nelson, Harvard University
Monday Mar 20, 2017 10:35 - 11:17
Optimal lower bound for samplers, finding duplicates, and universal relation
Qin Zhang, Indiana University
Monday Mar 20, 2017 11:19 - 11:43
Some New Questions in Communication Complexity
Adi Rosen, CNRS and U. Paris Diderot
Monday Mar 20, 2017 11:46 - 12:25
On Multi-Party Peer-to-Peer Information Complexity
Sivaramakrishnan Natarajan Ramamoorthy, University of Washington
Monday Mar 20, 2017 15:53 - 16:38
Lower bounds on non-adaptive data structures for median and predecessor search
Justin Thaler, Georgetown University
Monday Mar 20, 2017 16:50 - 17:37
A Nearly Optimal Lower Bound on the Approximate Degree of $AC^0$
Mika Goos, Stanford University
Tuesday Mar 21, 2017 09:04 - 10:06
Query-to-Communication Lifting
Grigory Yaroslavtsev, Indiana University
Tuesday Mar 21, 2017 10:34 - 11:19
Linear Sketching using Parities
Joshua Brody, Swarthmore College
Tuesday Mar 21, 2017 11:21 - 11:45
Non-adaptive Data Structure Lower Bounds for Predecessor Search
Ashwin Nayak, University of Waterloo
Tuesday Mar 21, 2017 11:50 - 12:32
Quantum information complexity
Omri Weinstein, Columbia University
Tuesday Mar 21, 2017 17:15 - 18:14
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds (Part I)
Alexander Sherstov, UCLA
Tuesday Mar 21, 2017 20:11 - 21:07
Compressing Interactive Communication under Product Distributions
Sebastian Pokutta, Georgia Tech
Wednesday Mar 22, 2017 09:10 - 10:11
Information Theory and Extended Formulations
Ankit Garg, Microsoft Research
Wednesday Mar 22, 2017 11:20 - 11:52
Lookup functions for separating randomized communication, quantum communication and approximate log-rank
Michael Kapralov, EPFL
Thursday Mar 23, 2017 09:09 - 10:01
Lower bounds for (Streaming) Approximation to MAX-CUT
David Woodruff, IBM
Thursday Mar 23, 2017 10:16 - 11:08
Sketching and Streaming Matrix Norms
Rotem Oshman, Tel-Aviv University
Thursday Mar 23, 2017 11:14 - 11:49
On The Communication Complexity of Property Testing in Graphs
Amit Chakrabarti, Dartmouth College
Thursday Mar 23, 2017 15:04 - 15:43
Strong Lower Bounds for Multi-Party Equality with Applications
Kasper Green Larsen, Aarhus University
Thursday Mar 23, 2017 15:48 - 16:31
Optimality of the Johnson-Lindenstrauss Lemma
T.S. Jayram , IBM Almaden Research Center
Thursday Mar 23, 2017 16:47 - 17:36
Common Randomness Generation
Arkadev Chattopadhyay, Tata Institute of Fundamental Research
Friday Mar 24, 2017 09:07 - 10:17
Topology Dependent Bounds on Rounds and Communication
Vladimir Braverman, Johns Hopkins University
Friday Mar 24, 2017 10:39 - 10:57
Streaming Symmetric Norms via Measure Concentration
