Near-Optimal Hardness Amplification from HDX
Russell Impagliazzo (UCSD)
Monday, October 20th 2025, 2-3pm
Abstract:
This talk will be a survey on hardness amplification, its use in derandomization, and connections to coding theory. However, I will endeavor to motivate and discuss the results in the above work in progress.
We use recent constructions of high-dimensional expanders to improve the rate of locally approximately list-decodable codes and the input size in hardness amplification for both uniform and non-uniform models.
Joint work with Yotam Dikstein, Max Hopkins and Toniann Pitassi