A quasilinear PCP theorem for PPAD

1 · The essentials

The manuscript describes a way to turn a particular search task into a collection of numerical checks. The collection is only moderately larger than the original input: its size grows by a factor bounded by a fixed power of the logarithm of the input size. A set of proposed numerical values need not pass every check, and the checks themselves allow a fixed amount of error. If the values pass enough checks, they can be used to recover an answer to the original task efficiently. This works regardless of which checks fail, provided their fraction stays within a fixed limit and the values have suitably bounded written representations. The manuscript also states that suitable values always exist. The main result has not been formalized in Lean or formally verified.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine replacing a search task with a worksheet of numerical checks. Even if a small fixed share of the checks fail, and the others are only approximately correct, the completed worksheet still lets you recover the answer. The image does not capture the precise restrictions on how the numbers are written or how the checks are constructed.

Why it matters

The source presents this as resolving the quasilinear PCP-for-PPAD conjecture of Babichenko, Papadimitriou, and Rubinstein. The significance is the combination of a small size increase and tolerance for failed or approximate checks. The guarantee is not limited to a specially chosen pattern of failures: it applies regardless of which gates fail.

2 · Going further

The precise claim concerns an End-of-Line instance of binary length $N$ . The manuscript states that there are fixed positive rational constants $ε$ and $δ$ and a deterministic polynomial-time reduction producing a generalized circuit of total binary length $N (lo g N)^{O (1)}$ . This is the quasilinear size bound named in the conjecture.

The recovery guarantee applies to any rational assignment of polynomial encoding length that $ε$ -satisfies all but a $δ$ fraction of the circuit's gates. From such an assignment, a solution to the original End-of-Line instance can be recovered in polynomial time, regardless of the locations of the failing gates. The abstract also states an existence guarantee: qualifying assignments always exist, with one fixed polynomial bound on their encoding length.

At the level described by the abstract, the approach is to transform the search instance into numerical circuit constraints and recover an original solution from an approximately satisfying assignment, even with some failed constraints. The supplied text does not describe the internal construction or the argument establishing these guarantees. It supplies only the main manuscript, so no relationship to companion manuscripts can be assessed.

Useful notions

Binary input length
Polynomial-time computation
Reductions between search tasks
Numerical circuit constraints
Approximate satisfaction

What was known before / what is new

Before

The source identifies the quasilinear-size PCP-for-PPAD statement as a conjecture of Babichenko, Papadimitriou, and Rubinstein. It does not describe earlier bounds, constructions, or partial results.

New

The manuscript claims a deterministic polynomial-time reduction with total output length $N (lo g N)^{O (1)}$ . Its recovery guarantee tolerates a fixed fraction of failed gates and fixed numerical error on the remaining gates, subject to the assignment's encoding-length restriction. It also states that qualifying rational assignments always exist under a single fixed polynomial encoding bound.

Limits and assumptions

The claim concerns End-of-Line inputs and the generalized circuits produced by the stated reduction, not arbitrary numerical constraint systems. Recovery requires a rational assignment of polynomial encoding length that meets the fixed $ε$ accuracy requirement on all but a $δ$ fraction of gates; it does not allow unrestricted error or arbitrarily many failures. The supplied abstract gives neither the values of these constants nor the internal construction. The main result is not formalized in Lean and has not been formally verified. The source identifies no further open questions.

Mini glossary

Quasilinear size: Here, an output-length bound of the form $N (lo g N)^{O (1)}$ for input length $N$ .
Reduction: The transformation from an End-of-Line instance to numerical circuit constraints that support recovery of an original solution.
Generalized circuit: The system of numerical gate constraints produced by the manuscript's reduction.
Rational assignment: A choice of rational numerical values for the circuit, whose written encoding length is restricted in the recovery guarantee.
Approximate satisfaction: Meeting a gate's numerical requirement to the fixed accuracy specified by $ε$ .

Keywords : PCP-for-PPAD · Quasilinear reduction · Robust local verification

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

Resolves the quasilinear PCP-for-PPAD conjecture. An End-of-Line instance of length N reduces to numerical circuit constraints of total length $N (lo g 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.

To be verified: the proof is written in the manuscript, but no software has checked it and no validation by independent mathematicians is established. It may contain errors.

Manuscripts in this family

★

The PCP-for-PPAD conjecture: a quasilinear reduction

25/09/2026

To be verified

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 (lo g 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.

PDF GitHub folder