Playlist: 23 videos

Interactive Complexity

0:32:46

Yes, There is an Oblivious RAM Lower Bound!

Kasper Green Larsen (Aarhaus University)
https://simons.berkeley.edu/talks/yes-there-oblivious-ram-lower-bound
Interactive Complexity
Visit talk page
0:31:0

Time-Space Tradeoffs for the Memory Game

Amit Chakrabarti (Dartmouth College)
https://simons.berkeley.edu/talks/time-space-tradeoffs-memory-game
Interactive Complexity
Visit talk page
1:5:26

Static Data Structure Lower Bounds Imply Rigidity

Omri Weinstein (Columbia University)
https://simons.berkeley.edu/talks/static-data-structure-lower-bounds-imply-rigidity
Interactive Complexity
Visit talk page
0:26:59

Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers

Siva Natarajan Ramamoorthy (University of Washington)
https://simons.berkeley.edu/talks/lower-bounds-non-adaptive-data-structures-maintaining-sets-numbers-sunflowers
Interactive Complexity
Visit talk page
0:37:57

Simulation beats Richness: New Data-Structure Lower Bounds

Arkadev Chattopadhyay (Tata Institute of Fundamental Research)
https://simons.berkeley.edu/talks/simulation-beats-richness-new-data-structure-lower-bounds
Interactive Complexity
Visit talk page
0:34:35

Why Extension-Based Proofs Fail

Faith Ellen (University of Toronto)
https://simons.berkeley.edu/talks/why-extension-based-proofs-fail
Interactive Complexity
Visit talk page
0:26:50

Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication

Diptarka Chakraborty (Charles University)
https://simons.berkeley.edu/talks/tight-cell-probe-bounds-succinct-boolean-matrix-vector-multiplication
Interactive Complexity
Visit talk page
1:5:33

Sparse MDS Matrices: Proof of the GM-MDS Conjecture

Shachar Lovett (UC San Diego)
https://simons.berkeley.edu/talks/root-rank-barrier-log-rank-conjecture
Interactive Complexity
Visit talk page
0:35:52

On the Deterministic Complexity of Counting Events in a Stream

T.S. Jayram (IBM Almaden)
https://simons.berkeley.edu/talks/tbd-25
Interactive Complexity
Visit talk page
0:29:39

Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation

Huacheng Yu (Harvard University)
https://simons.berkeley.edu/talks/optimal-lower-bounds-distributed-and-streaming-spanning-forest-computation
Interactive Complexity
Visit talk page