
Hard Functions from on High: Local List Decoding from HDX
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.