LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Stronger Cell Probe Lower Bounds via Local PRGs
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Stronger Cell Probe Lower Bounds via Local PRGs

64 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

Oliver Korten of Columbia University presents a new method for proving lower bounds on static data structures in Yao's classical cell probe model. He argues that the technique yields the strongest known lower bounds for any explicit problem in this model, quadratically stronger in space as a function of time, breaking a barrier that has stood for decades. The core idea is a new connection between the static cell probe model and NC0 generators, objects studied extensively in cryptography and more recently in work on range avoidance. The talk is joint work with Toniann Pitassi of Columbia University and Russell Impagliazzo of UC San Diego, delivered as part of the Computer Science and Discrete Mathematics seminar at the Institute for Advanced Study. It is aimed at an audience familiar with complexity theory and data structure lower bound techniques.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime1 h 4 m
Compared with MathematicsShorter than 72%
Source channelInstitute for Advanced Study (YouTube)