Computer Science/Discrete Mathematics Seminar II
Hard Functions from on High: Local List Decoding from HDX
Can we encode data in a way that it is recoverable even when 1) most data becomes corrupted, and 2) we can only read a sub-constant fraction of the database? This is the central question of local list decoding, a powerful tool from coding theory that plays a central role in interactive proofs, hardness amplification, and pseudorandomness. In this (two part) talk we overview the first construction of high rate (approximate) locally list decodable codes with error tolerance and efficiency approaching the information theoretic limits, built from new local algorithmic machinery for the powerful class of high dimensional expanders.
In part one of this talk, we will give a high-level overview of local list decoding and its role in hardness amplification and pseudorandom generators. We then overview the properties of our codes and their application to long-standing problems in coding and complexity including:
- Constant rate codes with sub-polynomial time local list decoding
- Constant rate codes with highly parallel list decoding (RNC^1)
- Input-preserving hardness amplification and near-linear time pseudorandom generators
Finally we give a simplified version of our construction and decoding algorithm built on a subspace hypergraph system.
Based on joint work with Yotam Dikstein, Russell Impagliazzo, and Toniann Pitassi.