The PCP-for-PPAD conjecture: a quasilinear reduction
We prove the quasilinear-size PCP-for-PPAD conjecture of Babichenko, Papadimitriou, and Rubinstein. There are fixed positive rational constants ε and δ and a deterministic polynomial-time reduction that transforms an End-of-Line instance of binary length N into a generalized circuit of total binary length \(N(\log N)^{O(1)}\). From any rational assignment of polynomial encoding length that ε-satisfies all but a δ fraction of the gates, a solution to the original End-of-Line instance can be recovered in polynomial time, regardless of which gates fail. Such assignments always exist, with one fixed polynomial bound on their encoding length.
Cite
@misc{OAI:The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026,
author = {{OpenAI}},
title = {{The PCP-for-PPAD conjecture: a quasilinear reduction}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026/paper.pdf}{OAI:The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026}},
year = {2026}
}