Browse › Theoretical computer science › 136 A quasilinear PCP theorem for PPAD
The PCP-for-PPAD conjecture: a quasilinear reduction
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
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.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Follow-up works
- Anagnostides, Daskalakis, Farina, Golowich, Sandholm, Zhang, Fixed Sets and the Hardness of Computing Correlated Equilibria (arXiv:2610.28141, 20 October 2026). Main Theorem 4(ii) (polynomial-precision hardness) is stated under the PCP-for-PPAD conjecture (Assumption 2.3). Footnote 2 notes "OpenAI recently claimed a proof of the required PCP-for-PPAD theorem", linking this manuscript, but the authors do not treat it as established "until it has been verified by human experts".
Formalization
- OpenAI, Generalized-circuit smoothing, perturbation stability and rational meshes (Lean source, accessed 2026-10-21). This partial development supplies supporting lemmas and a goal proposition
QuasilinearPCPStatement, while its scope comment explicitly leaves simultaneous totality, the uniform reduction, soundness, algorithm realization and complexity bounds unproved.
Related prior literature mentioned by others
- Yakov Babichenko, Christos Papadimitriou and Aviad Rubinstein, Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash (arXiv:1504.02411, 2015; revised 2025-09-05). The AI Proved What? exposition identifies this work as the source of the conjecture that the manuscript claims to resolve.
- Aviad Rubinstein, Settling the complexity of computing approximate two-player Nash equilibria (arXiv:1606.04550, 2016; revised 2016-08-29). The AI Proved What? exposition identifies its encoded-path geometry and holographic proof system as predecessors of the manuscript's construction, distinguishing its conditional Nash lower bound from the PCP-for-PPAD conjecture.
Possibly relevant literature (found by the agent, not checked)
- Irit Dinur, The PCP theorem by gap amplification (ECCC TR05-046, 2005; J. ACM 2007). Gives constant-query PCPs and locally testable codes of quasilinear length via expander-based gap amplification, the Boolean analogue of the paper's quasilinear-size bound $M\le AN\lceil\log_2(N+2)\rceil^b$.
Digests and expositions
- AI Proved What?, PCP for PPAD? A quasilinear, gate-robust reduction from End-of-Line (episode 136, October 2026). This illustrated exposition and transcript explain the claimed reduction, its outer and inner constructions, robustness to failed gates, and the limited scope of the accompanying Lean development. [AI-generated per source]
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 136
Independent sites; their content is not reviewed here.
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}
}Family 136: A quasilinear PCP theorem for PPAD
Resolves the quasilinear PCP-for-PPAD conjecture. An End-of-Line instance of length N reduces to numerical circuit constraints of total length $N(\log N)^{O(1)}$ such that any polynomially encoded rational assignment satisfying all but a fixed fraction to fixed accuracy yields an endpoint solution. Such assignments always exist, giving robust local verification with only quasilinear size overhead.
This is the only paper in this family.