Size-Efficient PCPs from High-Dimensional Expanders

The PCP theorem [AS98, ALM + 98, Din07] is a breakthrough in theoretical CS with a wide range of applications. In this article, we discuss the work of [BMVY25] that constructs improved probabilistically checkable proofs (PCPs) from high-dimensional expanders (HDX). Our goal is to explain the main components of their construction, while also giving historical context for how the key ideas emerged across the PCP, HDX and routing literature. We aim for a largely self-contained overview, with additional pointers for technical details. We focus on the following ingredients: PCPs from expanders [Din07]; the abstraction of direct product testing [GS00]; recent constructions of linear size direct product testers with small soundness [BM24, BLM24, DD24a, DD24c, DDL24], and the role of high-dimensional expansion in enabling these results. We then explain how [BMVY25] turned such direct product testers into PCPs via a new connection to fault-tolerant routing, and a construction of such algorithms for HDX. Finally, we conclude with some other applications that these techniques have found and future directions.