• Click on the titles of individual talks for abstract, slides and archived video.

–
Coffee and Check-In
–
Welcome Remarks
–
The Hardest Halfspace
Alexander Sherstov (UCLA)
–
Break
–
Lower Bounds for Elimination via Weak Regularity
Michal Koucky (Charles University)
–
Round Elimination using Triangular Discrimination
Amir Yehudayoff (Technion Israel Institute of Technology)
–
Lunch
–
Quantum Algorithms for Composed Functions With Shared Inputs
Justin Thaler (Georgetown University)
–
Open Problems in Number-On-Forehead Communication Complexity
Toni Pitassi (University of Toronto)
–
Break
–
Bounded Independence Plus Noise, and the Communication Complexity of Decoding
Emanuele Viola (Northeastern University)
–
Network Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All
Sumegha Garg (Princeton University)
–
Open Problem Session
–
Coffee and Check-In
–
Advances in Linear Sketching over Finite Fields
Grigory Yaroslavtsev (Indiana University, Bloomington)
–
Break
–
Strong Direct Sum for Randomized Query Complexity
Joshua Brody (Swarthmore College)
–
On a Composition Theorem for Randomized Query Complexity
Troy Lee (Nanyang Technological University)
–
Lunch
–
Distributed Interactive Proofs
Rotem Oshman (Tel Aviv University)
–
Yes, There is an Oblivious RAM Lower Bound!
Kasper Green Larsen (Aarhus University)
–
Break
–
Time-Space Tradeoffs for the Memory Game
Amit Chakrabarti (Dartmouth College)
–
Sparse Trace Reconstruction
Andrew McGregor (University of Massachusetts Amherst)
Reception
–
Coffee and Check-In
–
Static Data Structure Lower Bounds Imply Rigidity
Omri Weinstein (Columbia University)
–
Break
–
Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers
Siva Natarajan Ramamoorthy (University of Washington)
–
Simulation beats Richness: New Data-Structure Lower Bounds
Arkadev Chattopadhyay (Tata Institute of Fundamental Research)
–
Lunch
–
Why Extension-Based Proofs Fail
Faith Ellen (University of Toronto)
–
Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication
Diptarka Chakraborty (Charles University)
All workshop participants are cordially invited to the UC Berkeley Department of Electrical Engineering and Computer Sciences (EECS)'s ACM A.M. Turing Laureate Colloquium featuring a talk by 1995 laureate Manuel Blum.
–
Coffee and Check-In
–
Sparse MDS Matrices: Proof of the GM-MDS Conjecture
Shachar Lovett (UC San Diego)
–
Break
–
On the Deterministic Complexity of Counting Events in a Stream
T.S. Jayram (IBM Almaden)
–
Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation
Huacheng Yu (Harvard University)
–
Lunch
–
The Sketching Complexity of Graph and Hypergraph Counting
Michael Kapralov (Ecole Polytechnique Fédérale de Lausanne)
–
Distributed Statistical Estimation of Matrix Products with Applications
Qin Zhang (Indiana University, Bloomington)
–
Fully Understanding The Hashing Trick
Lior Kamma (Aarhus University)