Computer Science/Discrete Mathematics Seminar II

In this talk we will construct (approximate) locally list decodable codes from high dimensional expanders (HDXs).

Last week we saw that locally list decoding is a powerful tool from coding theory. We also got a subspace-based construction of approximate locally list decodable codes with quasilinear rate.

I will start my talk with a short recap of last week. Afterwards, we will dive deeper into the decoding algorithm of our construction, and distill some general properties that were important for our algorithm to succeed. Then in an attempt to improve the rate of the codes, we will appeal to high dimensional expanders, hypergraphs that are analogues of expander graphs, and see how they satisfy the general properties we need. En route, I will share some of my thoughts on why these objects were the right tool for the task to begin with.

Based on joint work with Max Hopkins, Russell Impagliazzo, and Toniann Pitassi.