Size-Efficient PCPs from High-Dimensional Expanders
ACM SIGACT News · 31.03.2026 · 57 (1) · 42-63
DOI: 10.1145/3802807.3802813 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM SIGACT News, online erschienen am 31.03.2026. Verfasst von Mitali Bafna. Die Arbeit nennt 53 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
APA
Bafna, M. (2026). Size-Efficient PCPs from High-Dimensional Expanders. ACM SIGACT News, 57(1), 42-63. https://doi.org/10.1145/3802807.3802813
Vancouver
Bafna M. Size-Efficient PCPs from High-Dimensional Expanders. ACM SIGACT News. 2026;57(1):42-63. doi:10.1145/3802807.3802813
BibTeX
@article{Bafna2026,
author = {Bafna, Mitali},
title = {Size-Efficient PCPs from High-Dimensional Expanders},
journal = {ACM SIGACT News},
year = {2026},
volume = {57},
number = {1},
pages = {42--63},
doi = {10.1145/3802807.3802813}
}
EUVIMED