Communication Complexity and Applications, II

Videos from BIRS Workshop 17w5147

, National University of Singapore
- 10:14
Direct product theorems in communication
Watch video | Download video: 201703200916-Jain.mp4 (168M)
, Harvard University
- 11:17
Optimal lower bound for samplers, finding duplicates, and universal relation
Watch video | Download video: 201703201035-Nelson.mp4 (164M)
, Indiana University
- 11:43
Some New Questions in Communication Complexity
Watch video | Download video: 201703201119-Zhang.mp4 (82M)
, CNRS and U. Paris Diderot
- 12:25
On Multi-Party Peer-to-Peer Information Complexity
Watch video | Download video: 201703201146-Rosen.mp4 (158M)
, University of Washington
- 16:38
Lower bounds on non-adaptive data structures for median and predecessor search
Watch video | Download video: 201703201553-NatarajanRamamoorthy.mp4 (137M)
, Georgetown University
- 17:37
A Nearly Optimal Lower Bound on the Approximate Degree of $AC^0$
Watch video | Download video: 201703201650-Thaler.mp4 (146M)
, Harvard University
- 10:06
Query-to-Communication Lifting
Watch video | Download video: 201703210904-Goos.mp4 (190M)
, Indiana University
- 11:19
Linear Sketching using Parities
Watch video | Download video: 201703211034-Yaroslavtsev.mp4 (140M)
, Swarthmore College
- 11:45
Non-adaptive Data Structure Lower Bounds for Predecessor Search
Watch video | Download video: 201703211121-Brody.mp4 (72M)
, University of Waterloo
- 12:32
Quantum information complexity
Watch video | Download video: 201703211150-Nayak.mp4 (136M)
, Columbia University
- 18:14
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds (Part I)
Watch video | Download video: 201703211715-Weinstein.mp4 (231M)
, UCLA
- 21:07
Compressing Interactive Communication under Product Distributions
Watch video | Download video: 201703212011-Sherstov.mp4 (220M)
, Georgia Tech
- 10:11
Information Theory and Extended Formulations
Watch video | Download video: 201703220910-Pokutta.mp4 (187M)
, University of Massachusetts Amherst
- 11:19
Testable Bounded Degree Graph Properties Are Random Order Streamable (Morteza via Skype)
Watch video | Download video: 201703221034-McGregor.mp4 (119M)
, Microsoft Research New England
- 11:52
Lookup functions for separating randomized communication, quantum communication and approximate log-rank
Watch video | Download video: 201703221120-Garg.mp4 (112M)
, EPFL
- 10:01
Lower bounds for (Streaming) Approximation to MAX-CUT
Watch video | Download video: 201703230909-Kapralov.mp4 (157M)
, IBM
- 11:08
Sketching and Streaming Matrix Norms
Watch video | Download video: 201703231016-Woodruff.mp4 (173M)
, Tel-Aviv University
- 11:49
On The Communication Complexity of Property Testing in Graphs
Watch video | Download video: 201703231114-Oshman.mp4 (154M)
, Dartmouth College
- 15:43
Strong Lower Bounds for Multi-Party Equality with Applications
Watch video | Download video: 201703231504-Chakrabarti.mp4 (116M)
, Aarhus University
- 16:31
Optimality of the Johnson-Lindenstrauss Lemma
Watch video | Download video: 201703231548-Larsen.mp4 (192M)
, IBM Almaden Research Center
- 17:36
Common Randomness Generation
Watch video | Download video: 201703231647-Jayram.mp4 (184M)
, Tata Institute of Fundamental Research
- 10:17
Topology Dependent Bounds on Rounds and Communication
Watch video | Download video: 201703240907-Chattopadhyay.mp4 (183M)
, Johns Hopkins University
- 10:57
Streaming Symmetric Norms via Measure Concentration
Watch video | Download video: 201703241039-Braverman.mp4 (50M)