
Local List Decoding from HDX II
Yotam Dikstein of the Institute for Advanced Study continues a two part seminar on building locally list decodable codes from high dimensional expanders. He opens with a recap of the prior session's subspace-based construction, which achieves approximate local list decoding with quasilinear rate, then works through the decoding algorithm in more detail, isolating the general properties that made it succeed. The second half turns to high dimensional expanders, hypergraph analogues of expander graphs, and shows how they satisfy those same properties while offering a path to better rates. Dikstein also discusses why these combinatorial objects turn out to be a natural fit for the problem. The talk draws on joint work with Max Hopkins, Russell Impagliazzo, and Toniann Pitassi, and is pitched at a discrete mathematics and theoretical computer science audience already familiar with coding theory basics. Delivered as part of the IAS Computer Science/Discrete Mathematics Seminar series.