Communication Complexity and Applications, III
Videos from BIRS Workshop
Alexander Sherstov, UCLA
Monday Jul 25, 2022 10:33 - 11:42
The Approximate Degree of DNF and CNF Formulas
Raghuvansh Saxena, Microsoft Research
Monday Jul 25, 2022 14:34 - 15:14
Separating the Communication Complexity of Truthful and Non-Truthful Algorithms for Combinatorial Auctions
Hamed Hatami, McGill University
Monday Jul 25, 2022 15:32 - 16:42
Lower Bound Methods for Sign-rank and their Limitations
Madhu Sudan, Harvard University
Tuesday Jul 26, 2022 09:08 - 10:18
Sketching and Streaming Complexity of Constraint Satisfaction Problems
Huacheng Yu, Princeton University
Tuesday Jul 26, 2022 10:34 - 11:12
Strong XOR Lemma for Communication with Bounded Rounds
Rotem Oshman, Tel Aviv University
Tuesday Jul 26, 2022 11:13 - 11:55
Distributed Certification
Michael Kapralov, EPFL
Tuesday Jul 26, 2022 13:35 - 14:13
Factorial Lower Bounds for (Almost) Random Order Streams
Robert Robere, McGill University
Tuesday Jul 26, 2022 14:13 - 15:14
Proofs, Circuits, and Communication
Nikhil Mande, Centrum Wiskunde & Informatica (CWI)
Tuesday Jul 26, 2022 15:36 - 16:08
Symmetry and Quantum Query-to-Communication Simulation
David Woodruff, CMU
Wednesday Jul 27, 2022 09:04 - 10:14
Memory Bounds for the Experts Problem
Kasper Green Larsen, Aarhus University
Wednesday Jul 27, 2022 10:30 - 11:07
Stronger 3SUM-Indexing Lower Bounds
Amir Yehudayoff, Technion-IIT
Wednesday Jul 27, 2022 11:07 - 11:47
Blocky Rank
Sepehr Assadi, Rutgers
Thursday Jul 28, 2022 09:08 - 10:08
Recent Advances in Multi-Pass Graph Streaming Lower Bounds
Andrew McGregor, University of Massachusetts Amherst
Thursday Jul 28, 2022 10:30 - 11:02
A Guide to Estimating Entropy for the Forgetful and Impatient
Klim Efremenko, Ben-Gurion University
Thursday Jul 28, 2022 14:00 - 15:00
Binary Codes with Resilience Beyond 1/4 via Interaction
Suhail Sherif, University of Lisbon
Thursday Jul 28, 2022 16:00 - 16:30
Two directions related to the Log-Approximate-Rank Conjecture
