LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Catalytic Tree Evaluation from Matching Vectors
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Catalytic Tree Evaluation from Matching Vectors

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

Seyoon Ragavan, a researcher at MIT, presents this Institute for Advanced Study Computer Science/Discrete Mathematics seminar on the tree evaluation problem, a key test case for understanding the relative power of time and space in computation. He reviews prior approaches, including the Cook-Mertz algorithm running in slightly super-logarithmic space, and the catalytic-computing model introduced by Buhrman et al., where an algorithm is given a full hard drive it must return unchanged after use. Ragavan then presents his own result, a catalytic algorithm for tree evaluation using logarithmic free space, polynomial time, and only subpolynomial catalytic space, improving on the earlier poly(n) catalytic space bound. The talk's central idea is a connection drawn between private information retrieval and tree evaluation, both reducible to evaluating a function on a masked input. The lecture is blackboard-and-slides mathematics aimed at specialists in complexity theory and space-bounded computation.

At a glance

Lecture facts

Runtime compared with the other 148 Computer Science lectures
Runtime1 h 26 m
Compared with Computer ScienceLonger than 84%
Source channelInstitute for Advanced Study (YouTube)