# A quasilinear PCP theorem for PPAD

> End-of-Line puzzles turn into number circuits only slightly bigger that tolerate many broken gates, the paper claims. Plain-English explainer with sources.

Canonical: https://closedform.nishachay.tech/e/openai-math-2026-136/
Last updated: 2026-10-14

**End-of-Line puzzles turn into number circuits only slightly bigger that tolerate many broken gates, the paper claims.**

**Trust:** Claimed, not checked · **Papers:** 1 · **First paper:** September 25, 2026 · **Field:** Theoretical computer science · **Entry:** 136

*Explained by AI.* Drafted by one AI model and checked sentence by sentence against the paper by a different one. Spot a mistake? Report an error.

PPAD is a class of search problems where a solution must exist for a parity reason. Babichenko, Papadimitriou and Rubinstein conjectured that its core puzzle can be rewritten as a number circuit only slightly longer than the input. That rewriting must still give an answer when a fixed fraction of gates are broken by an adversary. This paper claims to prove that conjecture. No Lean formalization is listed.

## At a glance

- **First step:** 2016 (Babichenko, Papadimitriou and Rubinstein, who posed the conjecture)
- **Significance:** Major. If the proof holds, it settles a stated conjecture that links robust checking with the complexity of equilibria.
- **Trust:** Claimed, not checked
- **Field:** Theoretical computer science (1 paper)

## The explanation

Think of a huge maze of one-way corridors. Each room has at most one way in and one way out. You stand in a room with an exit but no entrance. Follow the corridors and you must reach a dead end, a room with no exit. Ends come in pairs, so another end must exist. Finding one can still take an enormous number of steps.

That puzzle is End-of-Line. The rooms are bit strings, and two small circuits name each room's next and previous room. The input length N counts the full description of both circuits[1]. PPAD is the class of search problems built on this parity argument[2]. Finding a Nash equilibrium of a game is a famous member.

A generalized circuit is a second language for the same class[3]. Each wire carries a number between 0 and 1. Each gate demands a local rule, up to a small error ε[4]. Take an Add gate fed 0.3 and 0.5. Its output must sit within ε of 0.8. Fed 0.7 and 0.6, the sum caps at 1, so the output must sit within ε of 1.

In 2016, Babichenko, Papadimitriou and Rubinstein posed the PCP-for-PPAD conjecture[5]. It asks for a short rewrite of End-of-Line into such circuits. Both the numerical error and the fraction of broken gates must be fixed positive constants[5]. The broken-gate allowance is the hard part. The answer must come out even if an adversary chooses which gates fail[6]. Short means quasilinear: N times a fixed power of log N[7].

Put numbers on that. Take N equal to one million bits, so log₂ N is about 19.9. If the power of the log were 2, the circuit would be about 400 million bits long. A blowup like N² would instead be a trillion. The paper fixes some power but does not name it in its main statement.

Ordinary hardness proofs, even with constant error, do not give the short size[8]. In 2016 Rubinstein used encoded paths and a checkable proof system to show related hardness for two-player Nash equilibria. He left the conjecture open and flagged combining the pieces as a remaining question[9].

This paper claims to resolve the conjecture[10]. It gives fixed constants ε and δ and a deterministic rewrite into circuits of length N times a power of log N[11]. From any assignment that meets all but a δ fraction of gates, a solution to the maze can be recovered[12]. That holds whatever gates fail[12]. Such assignments always exist[13]. Neither tolerance shrinks as N grows[14].

The difficulty is needing two things at once: quasilinear total storage and robustness to a fixed fraction of failures[15]. The paper turns the maze into paths in a high-dimensional box, so an approximate fixed point lands on an endpoint. Each local step must be computable without reading the whole maze[16]. Rooms are stored as coded words, so a word with a few damaged symbols can still be decoded.

There is a limit to keep in view. Later papers derive lower bounds for computing equilibria from this conjecture. Those bounds also assume an extra exponential-time hypothesis. The paper's result concerns the rewrite itself, not those bounds[17].

How sure is this? No Lean formalization is listed for this paper in the openai/math release. So no computer proof checker has checked it. No specialist review has been published.

**What it doesn't show.** This does not prove new running-time lower bounds for Nash equilibria; those still need an extra hardness assumption.

## Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

## Hype check

Major only if the proof holds. The constants ε, δ and the power of log N are fixed but not given as small numbers. Equilibrium time bounds that use it still need an extra assumption. No Lean formalization is listed and no specialist review is published.

## Words used

- **PPAD:** A class of search problems whose solutions must exist by a parity argument about endpoints of paths.
- **End-of-Line:** The core PPAD puzzle: given circuits naming next and previous rooms, find an end of a path other than the start.
- **Generalized circuit:** A network of gates whose wires carry numbers in [0, 1], each gate checking a simple rule up to error ε.
- **Reduction:** An efficient way to rewrite one problem as another, so a solution to the second gives one to the first.
- **Quasilinear:** At most the input length times a fixed power of its logarithm.
- **PCP:** Probabilistically checkable proof: a format where checking a few spots reveals whether the whole is badly wrong.

## The original paper

- [The PCP-for-PPAD conjecture: a quasilinear reduction](https://github.com/openai/math/blob/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026/paper.pdf) - September 25, 2026

## Quoted lines from the paper (17)

[1] From [The PCP-for-PPAD conjecture: a quasilinear reduction](https://github.com/openai/math/blob/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026/paper.pdf):

> The input length $N\geq2$ includes the complete descriptions of both circuits and their input and output lists.

[2] From [The PCP-for-PPAD conjecture: a quasilinear reduction](https://github.com/openai/math/blob/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026/paper.pdf):

> The class PPAD organizes total search problems whose existence proofs are based on the parity of endpoints in a directed graph.

[3] From [The PCP-for-PPAD conjecture: a quasilinear reduction](https://github.com/openai/math/blob/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026/paper.pdf):

> Generalized circuits provide another useful language for this class: a solution assigns real values in $[0,1]$ to wires and approximately satisfies local arithmetic, comparison, and Boolean constraints.

[4] From [The PCP-for-PPAD conjecture: a quasilinear reduction](https://github.com/openai/math/blob/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026/paper.pdf):

> Generalized circuits provide another useful language for this class: a solution assigns real values in $[0,1]$ to wires and approximately satisfies local arithmetic, comparison, and Boolean constraints.

[5] From [The PCP-for-PPAD conjecture: a quasilinear reduction](https://github.com/openai/math/blob/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026/paper.pdf):

> Babichenko, Papadimitriou, and Rubinstein formulated the PCP-for-PPAD conjecture as a quasilinear reduction from End-of-Line to generalized circuits in which both the allowed numerical error and the allowed fraction of violated gates are positive constants.

[6] From [The PCP-for-PPAD conjecture: a quasilinear reduction](https://github.com/openai/math/blob/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026/paper.pdf):

> The failure fraction is the essential robustness requirement: the decoder must succeed even if an adversary chooses which constraints to violate.

[7] From [The PCP-for-PPAD conjecture: a quasilinear reduction](https://github.com/openai/math/blob/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026/paper.pdf):

> There are fixed positive rational constants $\eps$ and $\delta$ 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)}$.

[8] From [The PCP-for-PPAD conjecture: a quasilinear reduction](https://github.com/openai/math/blob/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026/paper.pdf):

> Ordinary polynomial-time PPAD-hardness, even with constant numerical error, does not provide it.

[9] From [The PCP-for-PPAD conjecture: a quasilinear reduction](https://github.com/openai/math/blob/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026/paper.pdf):

> It established quasipolynomial hardness for constant-error two-player Nash under the exponential-time hypothesis for PPAD, while leaving the PCP-for-PPAD conjecture open and identifying composition as a remaining question.

[10] From [The PCP-for-PPAD conjecture: a quasilinear reduction](https://github.com/openai/math/blob/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026/paper.pdf):

> We give a positive resolution of the quasilinear PCP-for-PPAD conjecture.

[11] From [The PCP-for-PPAD conjecture: a quasilinear reduction](https://github.com/openai/math/blob/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026/paper.pdf):

> There are fixed positive rational constants $\eps$ and $\delta$ 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)}$.

[12] From [The PCP-for-PPAD conjecture: a quasilinear reduction](https://github.com/openai/math/blob/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026/paper.pdf):

> From any rational assignment of polynomial encoding length that $\eps$-satisfies all but a $\delta$ fraction of the gates, a solution to the original End-of-Line instance can be recovered in polynomial time, regardless of which gates fail.

[13] From [The PCP-for-PPAD conjecture: a quasilinear reduction](https://github.com/openai/math/blob/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026/paper.pdf):

> Such assignments always exist, with one fixed polynomial bound on their encoding length.

[14] From [The PCP-for-PPAD conjecture: a quasilinear reduction](https://github.com/openai/math/blob/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026/paper.pdf):

> Neither tolerance tends to zero with $N$.

[15] From [The PCP-for-PPAD conjecture: a quasilinear reduction](https://github.com/openai/math/blob/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026/paper.pdf):

> The present reduction needs two further properties simultaneously: quasilinear total storage and robustness to an arbitrary fixed fraction of failed gates.

[16] From [The PCP-for-PPAD conjecture: a quasilinear reduction](https://github.com/openai/math/blob/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026/paper.pdf):

> The proof must also provide local numerical access to the field: it cannot inspect the entire encoded graph when computing one coordinate of $v$.

[17] From [The PCP-for-PPAD conjecture: a quasilinear reduction](https://github.com/openai/math/blob/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026/paper.pdf):

> These time lower bounds retain their additional exponential-time hypothesis; the result here concerns the conjectured reduction itself.

## Other sources

- [C. H. Papadimitriou, “On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence”, Journal of Computer and System Sciences 48(3) (1994), 498–532](https://doi.org/10.1016/S0022-0000(05)80063-7)
- [Y. Babichenko, C. H. Papadimitriou and A. Rubinstein, “Can Almost Everybody be Almost Happy?”, ITCS 2016, 1–9](https://arxiv.org/abs/1504.02411v4)
- [A. Rubinstein, “Settling the Complexity of Computing Approximate Two-Player Nash Equilibria”, FOCS 2016, 258–265](https://arxiv.org/abs/1606.04550v2)
- [A. Rubinstein, “Inapproximability of Nash Equilibrium”, SIAM Journal on Computing 47(3) (2018), 917–959](https://arxiv.org/abs/1405.3322v5)
- [A. Deligkas, J. Fearnley, A. Hollender and T. Melissourgos, “Pure-Circuit: Tight Inapproximability for PPAD”, Journal of the ACM 71(5) (2024)](https://arxiv.org/abs/2209.15149v3)
- [openai/math release notes (2026): model provenance and review status](https://github.com/openai/math/blob/main/README.md): “manuscripts and supporting proof artifacts produced by an internal OpenAI model”

## Related

- [Subpolynomial query complexity for log-concave sampling](https://closedform.nishachay.tech/e/openai-math-2026-139/) - Theoretical computer science
- [Memory–sample lower bounds for noiseless Gaussian regression](https://closedform.nishachay.tech/e/openai-math-2026-140/) - Theoretical computer science
- [The Courtade–Kumar and Hellinger conjectures](https://closedform.nishachay.tech/e/openai-math-2026-119/) - Theoretical computer science
- [Homogeneous depth-five lower bounds for iterated matrix multiplication](https://closedform.nishachay.tech/e/openai-math-2026-135/) - Theoretical computer science
- [One-tape time simulation in two-fifths-power space](https://closedform.nishachay.tech/e/openai-math-2026-137/) - Theoretical computer science
- [Theoretical computer science](https://closedform.nishachay.tech/science/mathematics/theoretical-computer-science/) - Field · 40 results
- [Open since the 2010s](https://closedform.nishachay.tech/open-since/2010s/) - Era · 31 results
- [Claimed, not yet checked](https://closedform.nishachay.tech/trust/claimed/) - Trust · 130 results
- [Report an error](https://github.com/nishachay/closed-form/issues/new?template=report-error.yml&labels=entry-error&title=%5Bentry%20136%5D%20)