LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Hard Functions from on High: Local List Decoding from HDX
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Hard Functions from on High: Local List Decoding from HDX

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

Max Hopkins, a researcher at the Institute for Advanced Study, presents this two part Computer Science/Discrete Mathematics seminar on local list decoding, a coding theory tool used in interactive proofs, hardness amplification, and pseudorandomness. He opens with the central question: can data be encoded so it remains recoverable even when most of it is corrupted and only a sub-constant fraction can be read? Hopkins then outlines the first construction of high rate, approximately locally list decodable codes that approach information theoretic limits, built using new algorithmic machinery for high dimensional expanders. He covers constant rate codes with sub-polynomial time local decoding, highly parallel list decoding in RNC^1, and near-linear time pseudorandom generators, before closing with a simplified version of the construction based on a subspace hypergraph system. The work is joint with Yotam Dikstein, Russell Impagliazzo, and Toniann Pitassi.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime2 h 7 m
Compared with MathematicsLonger than 98%
Source channelInstitute for Advanced Study (YouTube)