Size Efficient PCPs and Fault-tolerant Routing via HDX
Speaker:
Dor Minzer, Massachusetts Institute of Technology
Date and Time:
Friday, September 26, 2025 - 10:30am to 11:20am
Location:
Fields Institute, Room 230 and online
Abstract:
We will discuss recent PCP constructions based on high-dimensional expanders that achieve small soundness and quasi-linear size, which are two key properties of PCPs.
To do so we discuss the idea of "derandomized hardness amplification", which is a soundness amplifying procedure that only incurs a mild size blow-up, and show how to achieve it (in the context of PCPs) via high-dimensional expanders.
No special background will be assumed.
Based on joint works with Mitali Bafna, Noam Lifshitz, Nikhil Vyas and Zhiwei Yun.