A quasilinear PCP theorem for PPAD

Source and verification

This article explains family 136 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Preliminaries: total search and approximate circuits

A finite directed graph in which every vertex has at most one incoming and one outgoing edge is a union of paths and cycles. If one is given the beginning of a path, there must be another endpoint. Finding it can nevertheless be difficult when a small Boolean circuit describes a graph with exponentially many vertices.

This is the starting point of PPAD, a class of total search problems defined through reductions to End-of-Line. “Total” means that every legal instance has a solution; it does not assert an efficient way to find one. The relevant prerequisites are finite graphs, Boolean circuits, error-correcting codes, and the Brouwer fixed-point theorem. The coding constructions below are used through their stated interfaces.

For the manuscript’s normalized End-of-Line problem, two Boolean circuits give maps $S,P$ on $n$-bit strings, with

$$\begin{array}{c}P(0)=0,S(0)\ne 0,\\ P(S(0))=0.\end{array}$$

One must return $v\ne 0$ for which at least one consistency check fails:

$$P(S(v))\ne v\text{or}S(P(v))\ne v.$$

The input length $N$ is the full binary description of both circuits, including wiring and input/output lists. It is not the number $2^n$ of graph vertices.

A generalized circuit assigns a real number in $[0,1]$ to each node. Each gate owns its output node, but cycles are allowed. Numerical gates include copying, multiplication by a specified rational constant, and addition clipped to $[0,1]$. For example, an addition gate with inputs $a,b$ and output $z$ is satisfied when

$$|z-\min (a+b,1)|\le \epsilon .$$

A comparison gate must output near one when $a<b-\epsilon$, and near zero when $a>b+\epsilon$. In the intervening band it imposes no condition. Boolean gates interpret values at most $\epsilon$ as low and values at least $1-\epsilon$ as high; applicable implications must all hold.

There are two separate error allowances. The number $\epsilon$ permits numerical error at a satisfied gate. The number $\delta$ permits a fraction of entire gates to fail. All gates receive equal weight, and every occurrence of a node uses the same assigned value.

🏷️ The quasilinear reduction

Manuscript result

Family 136 claims fixed rational constants $0<\epsilon <1/10$ and $0<\delta <1$, and deterministic polynomial-time reduction and decoding algorithms, such that every End-of-Line instance of length $N$ produces a generalized circuit of full encoding length $M\le AN\lceil {\log }_2(N+2){\rceil }^b$. Every rational assignment of the prescribed polynomial encoding length satisfying at least a $1-\delta$ fraction of the gates decodes to an End-of-Line solution. Here $A,b$, the tolerances, and the witness-length polynomial are fixed independently of the instance. (OpenAI, 2026)

The term quasilinear concerns the output length. The theorem does not require the reduction itself to run in quasilinear time. Counting only the principal nodes would be insufficient: the bound includes all auxiliary gates, wiring indices, and rational parameters.

The analogy with a probabilistically checkable proof is robustness under many local failures. An approximate solution must retain globally useful information even if an adversary concentrates its allowed failures on carefully chosen gates. This is stronger than allowing numerical error while requiring every gate to be satisfied.

The decoder’s soundness analysis also covers real assignments meeting the failure budget. Rationality and the polynomial witness bound make the computational search problem finite. Neither tolerance tends to zero as $N$ grows.

🏷️ Why approximate solutions exist

The totality assertion is logically separate from hardness. The manuscript supplies a useful elementary argument: for any fixed rational $\epsilon <1/10$, every legal generalized circuit has a rational assignment satisfying all its gates.

Replace each gate by a continuous coordinate update on the cube. Numerical gates use their exact clipped operation. A comparison uses a continuous ramp that has already reached its endpoint when the input gap has magnitude $\epsilon /2$. For Boolean gates use a signal $h$ that is zero on $[0,2\epsilon ]$, one on $[1-2\epsilon ,1]$, and linear between these intervals. The updates for OR, AND, and NOT are respectively

$$\begin{array}{rl}\mathrm{OR}:& \max (h(a),h(b)),\\ \mathrm{AND}:& \min (h(a),h(b)),\\ \mathrm{NOT}:& 1-h(a).\end{array}$$

Unique ownership of output nodes makes these updates a well-defined continuous self-map. Brouwer supplies a fixed point $x^{\ast }$. Set

$$q=\lceil 20/\epsilon \rceil$$

and round each coordinate to the nearest multiple of $1/q$. The rounding error is at most $\epsilon /40$. An addition or subtraction gate incurs at most three such errors. If a comparison implication is triggered after rounding, the original gap still exceeds $\epsilon /2$, so its fixed-point output was exactly the required endpoint. If a Boolean input becomes low after rounding, its original value was below $2\epsilon$, where $h$ is identically zero; the high case is analogous.

Thus every gate remains satisfied. Since $q$ is fixed, each rational coordinate needs bounded precision and the complete witness has polynomial length. This proves existence without supplying an efficient algorithm to find the fixed point.

Threshold conventions

The comparison implications use strict inequalities, while Boolean low/high thresholds use weak inequalities. Increasing $\epsilon$ can activate a Boolean antecedent that was previously inactive. One should not silently infer monotonicity of the complete gate relation from the numerical error bounds alone.

🏷️ Encoding a path as a fixed-point problem

The geometric reduction embeds the implicitly represented graph into a cube whose coordinate blocks encode graph vertices. Codewords representing distinct graph vertices are separated. An edge is realized by a polygonal route through four blocks of coordinates: copy an endpoint, update a control block, change the other endpoint, and reset.

A bounded vector field points along these routes. Away from neighborhoods of genuine endpoints, a small clipped update has a definite nonzero displacement. Consequently, a sufficiently accurate fixed point must lie near an endpoint that can be decoded.

Two details prevent false solutions. The distinguished known source receives a special entry construction; otherwise that already known endpoint would itself solve the geometric problem. The field away from the embedded paths also receives an explicit prescription; merely specifying motion along the paths would leave uncontrolled zeros elsewhere.

The local circuit cannot inspect the full exponential graph. It must recognize nearby encoded vertices and their predecessors or successors through a small number of local reads. That requirement motivates the two coding layers.

🏷️ Outer representation and inner correction

The outer representation stores a locally evolving computation in $N\mathrm{polylog}N$ symbol positions, with symbols of polylogarithmic length. Its interface supplies constant-distance separation, local tests, local transition procedures, and a global decoder.

The main accounting problem is that a local tape edit can change many encoded checks. The construction prepares update certificates for the affected arrays and includes certificates for those updates. Their algebraic degree decreases through a bounded number of levels, making this closure finite. Long computations are performed sequentially with reused scratch space: elapsed computation length need not become stored representation length.

Local tests must also detect an invalid representation on a substantial fraction of checks. A single violated constraint would be too easy to hide inside the allowed gate-failure budget. Bundling certificates into the symbol structure is designed to retain a constant gap without adding so many unrelated tests that the gap is diluted.

The inner binary encoding turns each outer symbol into a binary block. Its fixed correction radius is chosen before later accuracy parameters. Repeating correction improves the required average accuracy over requested coordinates; it does not assert that every requested bit is always correct.

This distinction matters because geometric decisions can select which coordinate to use. The proof estimates a bounded list of hypothetical candidate computations before the eventual selection, rather than applying an average guarantee after conditioning on a favorable branch.

🏷️ Replication, synchronization, and adversarial failures

For each geometric coordinate, the circuit maintains many replicas. An averaging operator from an expander graph couples them. Schematically, satisfied update gates impose

$$X_{ir}\approx \mathrm{clip}((AX{)}_{ir}+\beta {\hat{v}}_{ir}(\bar{X})),$$

where $\bar{X}$ denotes replica means. The field estimates are bounded even when their internal decisions are wrong.

This boundedness permits coarse synchronization first: the spectral gap controls disagreement among replicas using only a small update size and the number of failed physical gates. Correctness of the functional decisions is established afterward. Reversing that order would make the argument circular.

Next, the proof charges inaccurate reads and gate failures to the computations they can affect. A bounded read multiplicity prevents one corrupted location from contaminating arbitrarily many outputs. Expensive shared computations distribute their designated outputs redundantly so that failures concentrated at extraction gates cannot destroy a whole cohort without paying the corresponding budget.

An unreliable decision inside otherwise satisfied numerical gates causes an error proportional to the small step $\beta$, apart from arithmetic tolerance. Treating it as an unrestricted order-one displacement would lose the needed estimate. Truly failed update gates use the coarser bounded-range estimate.

Finally, clipping must stay inside the comparison with the replica mean. Nonexpansiveness and the expander contraction imply that a small replica residual gives a small clipped mean residual. The geometric lower bound for displacement then forces the mean into an endpoint neighborhood.

Random tapes occur in the analysis of local procedures, but the final circuit is deterministic: the required finite tapes are enumerated. The estimates concern each hypothetical branch under the original tape law, avoiding an unjustified independence claim after conditioning on an adaptive execution.

🏷️ Interpretation and connections

The central mechanism is the conversion of globally concentrated gate damage into controlled average geometric error at quasilinear encoding cost. The coding and circuit-composition interfaces are essential parts of the claimed theorem; the geometric picture alone does not prove robustness.

The result is a search reduction. Quantitative time lower bounds require additional complexity assumptions and parameter-preserving reductions. Applications to approximate equilibria require their own translation of circuit errors into equilibrium errors.

Mean-payoff games gives another example of a computational problem whose solution is guaranteed to exist, while one-tape simulation illustrates why encoding size, running time, and workspace must be tracked separately.

🏷️ Key steps and proof outlines

Coarse synchronization does not assume a correct decoder

The robustness argument must first make replicas close enough for the local decoding rules to be reliable. It therefore cannot use decoder correctness to prove that closeness. The “Inner gadget” section avoids this circularity through a bound valid for every internally produced field estimate.

Let $X$ be the array of replica values, $\bar{X}$ its coordinatewise replica mean, and $A$ the expander averaging operator. On the mean-zero subspace assume $\Vert AD\Vert \le (1-\kappa )\Vert D\Vert$, where $\kappa >0$ is the fixed gap. Norms here are the manuscript’s normalized Euclidean replica norm. The field estimate is bounded by a fixed $B_1$, the update step is $\beta$, the arithmetic error tolerance is $\epsilon$, and a fraction at most ${\delta }_g$ of the invocation’s physical gates fail.

An unfailed direct computation changes its averaging input by at most a constant times $\beta B_1+\epsilon$, regardless of whether its decisions are right. Failed computations use the bounded coordinate range. Their contribution to normalized Euclidean error is proportional to $\sqrt{{\delta }_g}$. The source obtains

$$\kappa \Vert X-\bar{X}{\Vert }_{\mathrm{rep}}\le \Vert X-AX{\Vert }_{\mathrm{rep}}\le 4\beta B_1+2C_{\mathrm{ar}}\epsilon +6\sqrt{{\delta }_g}.$$

The first inequality follows by writing $D=X-\bar{X}$ and using $\Vert D\Vert \le \Vert D-AD\Vert +\Vert AD\Vert$. Choose the parameters to make the right side less than $\kappa d_{\mathrm{sync}}$, the decoding synchronization radius. No successful functional decision has been assumed yet. (OpenAI, 2026)

Incorrect decisions and failed gates have different costs

After synchronization, classify a computation as unstable if it has an ambiguous comparison at the mean, an excessive routed deviation, or a spoiled external comparison occurrence. Bounded routing multiplicity and the source’s hypothetical-branch estimates bound their fraction by $q_{\mathrm{bad}}$. On stable unfailed computations, the comparison margins dominate all arithmetic tolerances, so the local estimator obeys its fine accuracy bound.

An unstable but unfailed computation still executes a bounded field update. Its discrepancy from the correct field update is therefore $O(\beta )$, not order one. A truly failed update may have order-one discrepancy. Keeping these cases separate gives

$$\begin{array}{rl}{E}_{\mathrm{in}}& :=\Vert X-\mathrm{clip}(AX+\beta v(\bar{X})){\Vert }_{\mathrm{rep}}\\ & \le \beta (c_{\ast }\kappa /20+6B_1\sqrt{q_{\mathrm{bad}}})+2C_{\mathrm{ar}}\epsilon +6\sqrt{{\delta }_g}<\beta c_{\ast }\kappa /2.\end{array}$$

Here $c_{\ast }$ is the geometric displacement constant and $v$ is the ideal field. The tolerances are fixed in a dependency order that reserves this strict inequality. Treating every unstable comparison as an unrestricted failed update would remove the helpful factor $\beta$ and spoil that choice.

Clipping stays inside the contraction argument

Put $F=\mathrm{clip}(AX+\beta v(\bar{X}))$ and let $C_0=\mathrm{clip}(\bar{X}+\beta v(\bar{X}))$, repeated identically on replicas. Coordinatewise clipping is nonexpansive, so

$$\Vert F-C_0{\Vert }_{\mathrm{rep}}\le (1-\kappa )\Vert X-\bar{X}{\Vert }_{\mathrm{rep}}.$$

Projection onto mean-zero arrays minimizes distance to replica-constant arrays, giving the same bound for $F-\bar{F}$. Projecting $X-F$ onto that subspace yields $\Vert X-\bar{X}\Vert \le E_{\mathrm{in}}/\kappa$. Projecting onto means and comparing to $C_0$ then gives

$$\Vert \bar{X}-C_0{\Vert }_{\mathrm{b}}\le E_{\mathrm{in}}+(1-\kappa )\Vert X-\bar{X}{\Vert }_{\mathrm{rep}}\le E_{\mathrm{in}}/\kappa <c_{\ast }\beta .$$

The geometric lemma says that outside a $10\tau$ neighborhood of genuine endpoints, this clipped displacement is at least $c_{\ast }\beta$. The contradiction forces endpoint proximity. At no point is clipping assumed to commute with taking a mean; generally it does not.

The decoded endpoint must survive output extraction

A mean close to an endpoint is not itself a robust output circuit. The source discards replica coordinates whose mean is too far from the corresponding endpoint bit, then those whose individual deviation is too large. The squared-distance estimates control the discarded fractions by the elementary bound $\mathrm{Pr}(|Z|\ge a)\le \mathbb{E}|Z{|}^2/a^2$. The surviving coordinates have a definite threshold margin. Redundant designated outputs and bounded extraction multiplicity then ensure that destroying a substantial output fraction consumes a proportional fraction of physical failures.

This final accounting connects the analytic residual estimate to the actual End-of-Line decoder. It is also where counting every auxiliary gate and output occurrence matters: a small collection of unprotected extraction gates would otherwise let an adversary erase globally useful information at negligible cost. Together with the outer representation and its quasilinear encoding bound, this supplies the source’s claimed robust search reduction.

🏷️ Manuscripts and verification scope

• The PCP-for-PPAD conjecture: a quasilinear reduction — pinned manuscript and companion source.

No family scope page was present at lean/docs/136.md in the pinned snapshot. This does not establish that all related formalization code is absent. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. The PCP-for-PPAD conjecture: a quasilinear reduction.