EUVIMEDEUVIMED entdecken
Crossref

Size-Efficient PCPs from High-Dimensional Expanders

Mitali Bafna

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →