Search

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.

1 paper September 25, 2026 Explained by AI

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.

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. PPAD is the class of search problems built on this parity argument. Finding a Nash equilibrium of a game is a famous member.

A generalized circuit is a second language for the same class. Each wire carries a number between 0 and 1. Each gate demands a local rule, up to a small error ε. 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. 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. The broken-gate allowance is the hard part. The answer must come out even if an adversary chooses which gates fail. Short means quasilinear: N times a fixed power of log N.

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. 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.

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

The difficulty is needing two things at once: quasilinear total storage and robustness to a fixed fraction of failures. 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. 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.

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

All quoted lines (17)
  1. The input length N≥2N\geq2 includes the complete descriptions of both circuits and their input and output lists.
    The PCP-for-PPAD conjecture: a quasilinear reduction Back to text
  2. The class PPAD organizes total search problems whose existence proofs are based on the parity of endpoints in a directed graph.
    The PCP-for-PPAD conjecture: a quasilinear reduction Back to text
  3. Generalized circuits provide another useful language for this class: a solution assigns real values in [0,1][0,1] to wires and approximately satisfies local arithmetic, comparison, and Boolean constraints.
    The PCP-for-PPAD conjecture: a quasilinear reduction Back to text
  4. Generalized circuits provide another useful language for this class: a solution assigns real values in [0,1][0,1] to wires and approximately satisfies local arithmetic, comparison, and Boolean constraints.
    The PCP-for-PPAD conjecture: a quasilinear reduction Back to text
  5. 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.
    The PCP-for-PPAD conjecture: a quasilinear reduction Back to text
  6. The failure fraction is the essential robustness requirement: the decoder must succeed even if an adversary chooses which constraints to violate.
    The PCP-for-PPAD conjecture: a quasilinear reduction Back to text
  7. 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 NN into a generalized circuit of total binary length N(log⁡N)O(1)N(\log N)^{O(1)}.
    The PCP-for-PPAD conjecture: a quasilinear reduction Back to text
  8. Ordinary polynomial-time PPAD-hardness, even with constant numerical error, does not provide it.
    The PCP-for-PPAD conjecture: a quasilinear reduction Back to text
  9. 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.
    The PCP-for-PPAD conjecture: a quasilinear reduction Back to text
  10. We give a positive resolution of the quasilinear PCP-for-PPAD conjecture.
    The PCP-for-PPAD conjecture: a quasilinear reduction Back to text
  11. 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 NN into a generalized circuit of total binary length N(log⁡N)O(1)N(\log N)^{O(1)}.
    The PCP-for-PPAD conjecture: a quasilinear reduction Back to text
  12. 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.
    The PCP-for-PPAD conjecture: a quasilinear reduction Back to text
  13. Such assignments always exist, with one fixed polynomial bound on their encoding length.
    The PCP-for-PPAD conjecture: a quasilinear reduction Back to text
  14. Neither tolerance tends to zero with NN.
    The PCP-for-PPAD conjecture: a quasilinear reduction Back to text
  15. The present reduction needs two further properties simultaneously: quasilinear total storage and robustness to an arbitrary fixed fraction of failed gates.
    The PCP-for-PPAD conjecture: a quasilinear reduction Back to text
  16. The proof must also provide local numerical access to the field: it cannot inspect the entire encoded graph when computing one coordinate of vv.
    The PCP-for-PPAD conjecture: a quasilinear reduction Back to text
  17. These time lower bounds retain their additional exponential-time hypothesis; the result here concerns the conjectured reduction itself.
    The PCP-for-PPAD conjecture: a quasilinear reduction Back to text

Other sources

  1. 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
  2. Y. Babichenko, C. H. Papadimitriou and A. Rubinstein, “Can Almost Everybody be Almost Happy?”, ITCS 2016, 1–9
  3. A. Rubinstein, “Settling the Complexity of Computing Approximate Two-Player Nash Equilibria”, FOCS 2016, 258–265
  4. A. Rubinstein, “Inapproximability of Nash Equilibrium”, SIAM Journal on Computing 47(3) (2018), 917–959
  5. A. Deligkas, J. Fearnley, A. Hollender and T. Melissourgos, “Pure-Circuit: Tight Inapproximability for PPAD”, Journal of the ACM 71(5) (2024)
  6. openai/math release notes (2026): model provenance and review status manuscripts and supporting proof artifacts produced by an internal OpenAI model

Browse Theoretical computer science Open since the 2010sClaimed, not yet checked