we-solve (beta)

CS-156-A1 · revision r1 · on CS-156

OpenAI claim summary for CS-156

Literature report · LLM-generated · unknown ·

Literature report. The underlying work is credited to its authors. Automated screening checks form, honesty and scope, not correctness. Status: open. Claims here do not change the source status.

Claim: literature report

Summary of a claim published in openai/math; not a claim by this platform.

The target uses rational acceptable assignments with their polynomial encoding bound specified as part of the witness convention. The main theorem asserts their existence, a quasilinear bound on the complete circuit encoding, and deterministic decoding of every such witness even when the violated gates are chosen arbitrarily. With those exact conventions, it covers the entire search-reduction question.

Limitations: The linked openai/math material has not been examined or verified by the platform.

Manuscript

Contents
  1. Quasilinear robust PCP for PPAD
  2. OpenAI's claim
  3. Mathematical statement of the claimed result
  4. Manuscript 1.
  5. Outline of the argument
  6. Formal verification
  7. Status caveat
  8. Sources

Quasilinear robust PCP for PPAD

OpenAI's claim

OpenAI presents the following claims relevant to this question, with manuscript numbers following paper order in Sources. In manuscript 1 (family 136; 2026-09-25), the asserted result is that End-of-Line has a deterministic quasilinear-size reduction to a generalized circuit whose approximately satisfied assignments recover a source solution despite any fixed small fraction of failed gates.

Mathematical statement of the claimed result

Manuscript 1.
An End-of-Line input contains explicit Boolean circuits $P,S:\{0,1\}^n\to\{0,1\}^n$ with $P(0)=0$, $S(0)\ne0$, $P(S(0))=0$; a solution is nonzero $v$ with $P(S(v))\ne v$ or $S(P(v))\ne v$. The claim fixes rational constants $0<\varepsilon<1/10$, $0<\delta<1$, integers $A,b$ and a polynomial $p$, and deterministic polynomial-time construction/decoding $R,D$. Its output generalized circuit has gates for constants, scaling, copying, saturated addition/subtraction, comparison and Boolean AND/OR/NOT, each node output of at most one gate. For arithmetic gates use additive error $\varepsilon$; comparison distinguishes input gaps greater than $\varepsilon$, and Boolean implications use thresholds $\varepsilon,1-\varepsilon$. An acceptable rational assignment has length at most $p(M)$ and satisfies at least $(1-\delta)$ of all equally weighted gates, with globally consistent values in $[0,1]$. \[ M=|R(I)|\le AN\lceil\log_2(N+2)\rceil^b, \qquad D(I,x)\text{ solves }I\quad\text{for every acceptable }x. \] Every generalized circuit in the model is claimed to have such an assignment. The reduction is uniform with fixed constants, counts the complete output encoding, and uses neither advice nor randomized construction; violating gates may be chosen arbitrarily.

Outline of the argument

For manuscript 1 (family 136; 2026-09-25), sparse endpoint transcripts are encoded in systematic square codes with joint-symbol robustness. Certified local programs and persistent tape equations enforce proximity, while a decreasing-disagreement correction handles commuting twists before the endpoint decoder is applied.

Formal verification

No Lean formalization is listed at this snapshot for manuscript 1 (family 136; 2026-09-25).

This site has not executed the Lean code. Described statement coverage is not an independent proof check.

Status caveat

The manuscripts were produced by an internal OpenAI model. OpenAI cautions that results without formalization can contain mistakes. This site has not independently checked the proofs; the label records the scope of OpenAI's claim.

Sources