PCP for PPAD?

0:00End-of-Line and generalized circuits

Some search problems always have a solution, for a parity reason. In End-of-Line, two circuits name each n-bit string’s successor and predecessor, and the all-zero string starts a path. Follow it, and it must end somewhere; that end, or any other place where a path starts or stops, is a solution. The class PPAD collects problems like this, and finding a Nash equilibrium of a two-player game is one of them. The standard bridge between the two is a generalized circuit: wires carry numbers between zero and one, and gates that set constants, copy, add, subtract, scale, compare, or act like logic gates must hold up to an error ε. In our check, a comparator that tests its own output against a constant one half is forced into the middle: every assignment satisfying its gates keeps that wire within 2ε of one half. Chen, Deng and Teng developed generalized circuits; similar arithmetic and logic gadgets underlie the equilibrium reductions of Daskalakis, Goldberg and Papadimitriou. Rubinstein showed hardness when the error ε is a constant, but with every gate required to hold. Babichenko, Papadimitriou and Rubinstein conjectured a stronger, PCP-like version: a reduction from End-of-Line of only quasilinear size, in which the error and the fraction of gates allowed to fail are both positive constants. The decoder must then work even when an adversary picks which gates to break. In 2016, Rubinstein combined encoded paths with a holographic proof system to show quasipolynomial hardness for constant-error Nash equilibria in two-player games, assuming an exponential time hypothesis for PPAD, but left this conjecture open.

1:49The claim

Result 136 is a single OpenAI preprint, 147 pages, dated September 25. It claims a proof of the quasilinear conjecture. There are fixed constants, ε below 1/10 and δ, and a deterministic polynomial-time reduction that turns an End-of-Line instance of length N into a generalized circuit of length at most a constant times N times a fixed power of log N. From any assignment that satisfies all but a δ fraction of the gates to within ε, wherever the failures fall, a decoder recovers a solution in polynomial time. And such assignments always exist, by Brouwer’s fixed point theorem and rounding to a grid. The constants exist but are not given: ε, δ and the power of the logarithm come out of a long chain of choices, and are never computed. The paper also derives PPAD-hardness for approximate equilibria in several games and markets, but through earlier reductions that need only robustness to a constant fraction of broken gates, not the quasilinear size, and running-time lower bounds still need the exponential time hypothesis for PPAD. There is no Lean formalization of the theorem: a partial Lean file states it and proves only supporting lemmas.

3:09How the proof goes

The proof follows Rubinstein’s geometry. Give each vertex a well-separated binary codeword, and turn every edge into a short route through a box whose dimension is four times the codeword length: change the second block, raise a flag, change the first block, lower the flag. Corners are rounded, and a field pushes points along these routes. Away from the endpoints, every point moves by a definite amount, so anything that is nearly a fixed point sits near an endpoint, and an endpoint’s first block names a solution. The difficulty is that the circuit must compute this field locally, and doing that robustly, directly on N-bit vertices, would cost a polynomial in N. So the construction works at two scales. The outer scale rewrites the graph so that each step changes at most one tape bit, plus a marker saying whether that cell is in use, and encodes vertices as words of short symbols, indexed by a group of quasilinear size: binary vectors, shuffled by projective linear groups over three primes; Helfgott’s ternary Goldbach theorem supplies three primes with the right sum. Checking is done by certificates, not sampling: residuals become polynomial remainders, so a single false equation produces a nonzero codeword at constant distance. Because one tape edit changes every encoded array, the construction prepares differences instead, one small group of Fourier frequencies at a time. The inner scale applies a fixed robust gadget, built from low-degree tests and expander codes, only to symbols of polylogarithmic length, where its polynomial cost is affordable. Finally, each coordinate of the point is held by many replicas, coupled by an averaging operator on a grid, a Margulis–Gabber–Galil expander with a spectral gap of at least 1/100. Expensive gadgets are shared, and every comparison gets its own routed read. Now let an adversary break a δ fraction of the gates. First, the replicas stay synchronized, without assuming any decision is correct. Second, once synchronized, all but a small fraction compute the true field. Third, the average point barely moves under one step of the field, so it lies near an endpoint, and rounding its first block decodes a solution, without knowing which gates failed. In our check, the averaging operator’s second eigenvalue stayed between 0.75 and 0.89 for eight grid sizes, from side 2 to 25, below the paper’s bound of 0.942.

5:42Where it stands

The preprint is not peer reviewed and has not been revised. There is no Lean formalization of the theorem; a partial Lean file states it and proves only supporting lemmas. The paper is not among those OSVerify reviewed, and we have seen no expert review. If it holds, the PCP for PPAD conjecture of Babichenko, Papadimitriou and Rubinstein is true: End-of-Line reduces, with only polylogarithmic overhead, to numerical circuits that stay hard even when a constant fraction of the gates may be broken. Turning that into concrete running-time lower bounds for equilibria still needs an exponential time hypothesis for PPAD.