Communication Complexity and Applications, III

Videos from BIRS Workshop

, UCLA
- 11:42
The Approximate Degree of DNF and CNF Formulas
Watch video | Download video: 202207251033-Sherstov.mp4 (72M)
, Microsoft Research
- 15:14
Separating the Communication Complexity of Truthful and Non-Truthful Algorithms for Combinatorial Auctions
Watch video | Download video: 202207251434-Saxena.mp4 (52M)
, McGill University
- 16:42
Lower Bound Methods for Sign-rank and their Limitations
Watch video | Download video: 202207251532-Hatami.mp4 (232M)
, Harvard University
- 10:18
Sketching and Streaming Complexity of Constraint Satisfaction Problems
Watch video | Download video: 202207260908-Sudan.mp4 (90M)
, Princeton University
- 11:12
Strong XOR Lemma for Communication with Bounded Rounds
Watch video | Download video: 202207261034-Yu.mp4 (42M)
, Tel Aviv University
- 11:55
Distributed Certification
Watch video | Download video: 202207261113-Oshman.mp4 (128M)
, EPFL
- 14:13
Factorial Lower Bounds for (Almost) Random Order Streams
Watch video | Download video: 202207261335-Kapralov.mp4 (45M)
, McGill University
- 15:14
Proofs, Circuits, and Communication
Watch video | Download video: 202207261413-Robere.mp4 (243M)
, Centrum Wiskunde & Informatica (CWI)
- 16:08
Symmetry and Quantum Query-to-Communication Simulation
Watch video | Download video: 202207261536-Mande.mp4 (36M)
, CMU
- 10:14
Memory Bounds for the Experts Problem
Watch video | Download video: 202207270904-Woodruff.mp4 (111M)
, Aarhus University
- 11:07
Stronger 3SUM-Indexing Lower Bounds
Watch video | Download video: 202207271030-Larsen.mp4 (177M)
, Technion-IIT
- 11:47
Blocky Rank
Watch video | Download video: 202207271107-Yehudayoff.mp4 (180M)
, Rutgers
- 10:08
Recent Advances in Multi-Pass Graph Streaming Lower Bounds
Watch video | Download video: 202207280908-Assadi.mp4 (72M)
, University of Massachusetts Amherst
- 11:02
A Guide to Estimating Entropy for the Forgetful and Impatient
Watch video | Download video: 202207281030-McGregor.mp4 (35M)
, Ben-Gurion University
- 15:00
Binary Codes with Resilience Beyond 1/4 via Interaction
Watch video | Download video: 202207281400-Efremenko.mp4 (101M)
, University of Lisbon
- 16:30
Two directions related to the Log-Approximate-Rank Conjecture
Watch video | Download video: 202207281600-Sherif.mp4 (63M)