Simulation beats Richness: New Data-Structure Lower Bounds

Channel:

Subscribers:

68,700

Published on October 17, 2018 7:49:42 PM ● Video Link: https://www.youtube.com/watch?v=lv6uIjamlc8

Duration: 37:57

245 views

Other Videos By Simons Institute for the Theory of Computing

2018-10-29	Robust List Decoding of Spherical Gaussians
2018-10-24	Mathematical Theories of Communication: Old and New
2018-10-18	Fully Understanding The Hashing Trick
2018-10-18	Distributed Statistical Estimation of Matrix Products with Applications
2018-10-18	The Sketching Complexity of Graph and Hypergraph Counting
2018-10-18	Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation
2018-10-18	On the Deterministic Complexity of Counting Events in a Stream
2018-10-18	Sparse MDS Matrices: Proof of the GM-MDS Conjecture
2018-10-17	Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication
2018-10-17	Why Extension-Based Proofs Fail
2018-10-17	Simulation beats Richness: New Data-Structure Lower Bounds
2018-10-17	Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers
2018-10-17	Static Data Structure Lower Bounds Imply Rigidity
2018-10-16	Time-Space Tradeoffs for the Memory Game
2018-10-16	Yes, There is an Oblivious RAM Lower Bound!
2018-10-16	Distributed Interactive Proofs
2018-10-16	On a Composition Theorem for Randomized Query Complexity
2018-10-16	Strong Direct Sum for Randomized Query Complexity
2018-10-16	Advances in Linear Sketching over Finite Fields
2018-10-15	Network Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All
2018-10-15	Bounded Independence Plus Noise, and the Communication Complexity of Decoding

Tags:

Simons Institute

Theory of Computing

Theory of Computation

Theoretical Computer Science

Computer Science

UC Berkeley

Interactive Complexity

Arkadev Chattopadhyay