betaFeedback

WorksMathematics

The PCP-for-PPAD conjecture: a quasilinear reduction

Abstract

We prove the quasilinear-size PCP-for-PPAD conjecture of Babichenko, Papadimitriou, and Rubinstein. There are fixed positive rational constants ε\varepsilon 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)}. From any rational assignment of polynomial encoding length that ε\varepsilon-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. Such assignments always exist, with one fixed polynomial bound on their encoding length.

Introduction and the exact search relation

The class PPAD organizes total search problems whose existence proofs are based on the parity of endpoints in a directed graph [27]. Its canonical problem, End-of-Line, asks for an endpoint other than a specified source, when the graph is described by predecessor and successor circuits. 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 generalized-circuit intermediary was developed by Chen, Deng, and Teng [10] (Section 4.2); arithmetic, comparison, and Boolean gadgets also underlie the equilibrium reductions of Daskalakis, Goldberg, and Papadimitriou [12] (Section 5.1). Rubinstein established constant-error hardness with every gate required to be satisfied [30] (Theorem 2). These results motivate the circuit language used here, with the precise normalization and thresholds specified below.

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 [2] (Conjecture 2). The failure fraction is the essential robustness requirement: the decoder must succeed even if an adversary chooses which constraints to violate. The quasilinear size requirement is a separate restriction on the reduction. Ordinary polynomial-time PPAD-hardness, even with constant numerical error, does not provide it. For example, hardness for every numerical error below 1/101/10 is known for the standard generalized-circuit problem with every gate required to be satisfied [14] (Theorem 4.1). Subsequent uses of PCP-for-PPAD also consider the weaker conjecture asserting ordinary PPAD-hardness with a positive failure fraction; the distinction from the original quasilinear formulation is explicit in [15] (Section 2.2.2).

Rubinstein’s 2016 work combined encoded-path geometry, a locally evolving version of End-of-Line, and a holographic proof system whose certificates can be constructed and decoded through restricted access [29] (Sections 3, 5, and 6). 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 [29] (Theorem 1.2 and Section 1.3). More recently, Golowich derives sharper two-player Nash lower bounds for vanishing approximation error under PCP for PPAD together with the exponential-time hypothesis for PPAD [22] (Theorem 1.1). These time lower bounds retain their additional exponential-time hypothesis; the result here concerns the conjectured reduction itself.

We give a positive resolution of the quasilinear PCP-for-PPAD conjecture. Our size bound counts the complete finite output, including connection indices, every auxiliary gate, and the bits of all rational parameters. The gate conventions below are the standard bounded-rational conventions of [14, 15]; the totality and witness-size statement is proved explicitly. When restricted to the nearly linear predecessor and successor circuits in the original formulation, the theorem gives the conjectured quasilinear reduction there as well.1

The source and target problems

We fix conventional explicit binary encodings of circuit gate lists, connection indices, input and output lists, and rational parameters. Integers are encoded in binary with delimiters. All size bounds concern these complete encodings. Changing between the usual such explicit encodings changes only constant or logarithmic factors.

Definition 1.1 (End-of-Line). An instance II consists of two explicitly listed, acyclic, bounded-fanin Boolean circuits

S,P:{0,1}n→{0,1}n,n≥1,S, P : \{0,1\}^{n} \to\{0,1\}^{n}, \qquad n \ge1,

using AND, OR, and NOT gates, with unrestricted fan-out, and satisfying

P(0n)=0n,S(0n)≠0n,P(S(0n))=0n.P(0^{n}) = 0^{n}, \qquad S(0^{n}) \ne0^{n}, \qquad P(S(0^{n})) = 0^{n}.

A solution is a string v≠0nv \ne0^{n} such that

P(S(v))≠vorS(P(v))≠v.P(S(v)) \ne v \quad\text{or} \quad S(P(v)) \ne v.

The input length N≥2N \ge2 includes the complete descriptions of both circuits and their input and output lists.

Definition 1.2 (Generalized circuit). A generalized circuit G=(V,T)G = (V,T) has an explicitly listed finite set of nodes VV and a nonempty set of gates TT. Each gate has one output and at most two inputs. A node is the output of at most one gate. Directed cycles and unrestricted fan-out are permitted. Every gate parameter α\alpha is a binary-encoded rational in [0,1][0,1].

For an assignment x:V→[0,1]x: V \to[0,1], write xa,xbx_a,x_b for input values and xzx_z for the output. The five arithmetic gate types are ε\varepsilon-satisfied when the corresponding condition holds:

Constant⁡(α;z):∣xz−α∣≤ε,Scale⁡(α;a;z):∣xz−αxa∣≤ε,Copy⁡(a;z):∣xz−xa∣≤ε,Add⁡(a,b;z):∣xz−min⁡{xa+xb,1}∣≤ε,Subtract⁡(a,b;z):∣xz−max⁡{xa−xb,0}∣≤ε.\begin{aligned} \operatorname{Constant}(\alpha;z):\quad&|x_z-\alpha|\le\varepsilon,\\ \operatorname{Scale}(\alpha;a;z):\quad&|x_z-\alpha x_a|\le\varepsilon,\\ \operatorname{Copy}(a;z):\quad&|x_z-x_a|\le\varepsilon,\\ \operatorname{Add}(a,b;z):\quad&|x_z-\min\{x_a+x_b,1\}|\le\varepsilon,\\ \operatorname{Subtract}(a,b;z):\quad&|x_z-\max\{x_a-x_b,0\}|\le\varepsilon. \end{aligned}

The comparison gate Less⁡(a,b;z)\operatorname{Less}(a,b;z) has the two implications

xa<xb−ε ⟹ xz≥1−ε,xa>xb+ε ⟹ xz≤ε.x_a<x_b-\varepsilon\ \Longrightarrow\ x_z\ge1-\varepsilon,\qquad x_a>x_b+\varepsilon\ \Longrightarrow\ x_z\le\varepsilon.

The Boolean gates have the following implications:

Or⁡(a,b;z):(xa≥1−ε or xb≥1−ε)⟹xz≥1−ε,(xa≤ε and xb≤ε)⟹xz≤ε;And⁡(a,b;z):(xa≥1−ε and xb≥1−ε)⟹xz≥1−ε,(xa≤ε or xb≤ε)⟹xz≤ε;Not⁡(a;z):xa≤ε⟹xz≥1−ε,xa≥1−ε⟹xz≤ε.\begin{aligned} \operatorname{Or}(a,b;z):\quad&(x_a\ge1-\varepsilon\ \text{or}\ x_b\ge1-\varepsilon)\Longrightarrow x_z\ge1-\varepsilon,\\ &(x_a\le\varepsilon\ \text{and}\ x_b\le\varepsilon)\Longrightarrow x_z\le\varepsilon;\\ \operatorname{And}(a,b;z):\quad&(x_a\ge1-\varepsilon\ \text{and}\ x_b\ge1-\varepsilon)\Longrightarrow x_z\ge1-\varepsilon,\\ &(x_a\le\varepsilon\ \text{or}\ x_b\le\varepsilon)\Longrightarrow x_z\le\varepsilon;\\ \operatorname{Not}(a;z):\quad&x_a\le\varepsilon\Longrightarrow x_z\ge1-\varepsilon,\\ &x_a\ge1-\varepsilon\Longrightarrow x_z\le\varepsilon. \end{aligned}

For these four gate types, every applicable implication must hold. If no antecedent holds, any output in [0,1][0,1] is permitted. In particular, the comparison thresholds are strict and the Boolean thresholds are weak.

Let MM be the complete binary encoding length of GG. For fixed ε,δ>0\varepsilon,\delta>0 and a fixed polynomial pp, an acceptable assignment is rational, has total binary encoding length at most p(M)p(M), and ε\varepsilon-satisfies at least (1−δ)∣T∣(1-\delta)|T| gates. Each gate has equal weight; at most ⌊δ∣T∣⌋\lfloor\delta|T|\rfloor gates may fail. Failed gates may violate their relations arbitrarily, but all their nodes still have one globally consistent value in [0,1][0,1].

The Boolean predicates make the error parameter nonmonotone: increasing ε\varepsilon can activate an antecedent that was previously vacuous. This issue is analyzed by Schuldenzucker and Seuken [31], Proposition 1. Our gate arguments use one actual tolerance throughout. Later upper bounds on that tolerance ensure explicit margins; they do not reclassify a satisfied Boolean gate at a larger tolerance.

Main theorem

Theorem 1.3 (Quasilinear PCP for PPAD). There are fixed rational constants 0<ε<1100 < \varepsilon< \frac{1}{10}, 0<δ<10 < \delta< 1, a fixed positive integer AA, a fixed nonnegative integer bb, a fixed polynomial pp with nonnegative integer coefficients, and deterministic algorithms RR, DD with the following properties.

(i) Every generalized circuit in Definition 1.2 has an acceptable rational assignment of encoding length at most p(M)p(M).

(ii) For every End-of-Line instance II of length NN, the output R(I)R(I) is a generalized circuit whose complete encoding length satisfies

M≤AN⌈log⁡2(N+2)⌉b.M \le AN\left\lceil\log_2(N+2) \right\rceil^b.

(iii) The construction RR runs in time polynomial in NN, with one fixed polynomial bound.

(iv) For every acceptable assignment xx of R(I)R(I), the algorithm D(I,x)D(I,x) returns a solution of II in time polynomial in NN plus the encoding length of xx, with one fixed polynomial bound.

All constants, polynomials, and algorithms are chosen once. They use no advice depending on the input length and no randomized construction.

The conclusion about DD is universal over the locations and values of the failed gates. In fact, the soundness argument applies to arbitrary real assignments meeting the gate-failure budget; rationality is needed for the finite search relation and its computational decoder. The totality proof supplies an assignment satisfying every gate on a fixed rational mesh. Neither tolerance tends to zero with NN.

Proof strategy: encoded paths and robust local computation

We begin with the geometric target of the reduction. Replace the End-of-Line graph by a locally evolving directed graph with a known source, no isolated vertices, and the same endpoint-decoding property. Represent each vertex ww by a separated binary word Ew∈{0,1}mE_w \in\{0,1\}^m. In the box [−1,2]4m[-1,2]^{4m}, viewed as four blocks of mm coordinates, each edge u→vu \to v traces a polygon that first changes a copy of EuE_u to EvE_v, changes a repeated control bit, updates the other copy, and resets the control bit. Rounded corners join these polygons into paths and cycles. An additional segment enters the known source, and a separate field prescription handles its far end. Every other path endpoint encodes an End-of-Line answer.

Section 10 constructs a bounded displacement field vv on this box. Close to a path it uses the directed tangent and the inward normal; farther away it passes to a fixed direction. For a sufficiently small fixed step β>0\beta> 0, the clipped move clip⁡(X+βv(X))−X\operatorname{clip}(X+\beta v(X))-X has norm at least a fixed positive multiple of β\beta outside a fixed neighborhood of the desired endpoints. Here clipping keeps each coordinate in the box, and the norm is normalized by the word length. Thus an accurate enough approximate fixed point identifies an endpoint. The proof must also provide local numerical access to the field: it cannot inspect the entire encoded graph when computing one coordinate of vv.

This use of encoded paths and restricted access has a close predecessor in Rubinstein’s holographic proof system [29], Sections 3, 5, and 6. The present reduction needs two further properties simultaneously: quasilinear total storage and robustness to an arbitrary fixed fraction of failed gates. The two scales of the construction address these requirements as follows.

A quasilinear outer word. Sections 2–5 construct canonical representations

Rw=(sk)k∈Γ,sk∈{0,1}L,∣Γ∣=N(log⁡N)O(1),L=(log⁡N)O(1).R_w=(s_k)_{k\in\Gamma},\qquad s_k\in\{0,1\}^{L},\qquad|\Gamma|=N(\log N)^{O(1)},\qquad L=(\log N)^{O(1)}.

A bounded number of symbol positions suffices to test local validity, propose a neighboring symbol, or perform one correction step. Each such operation has Boolean complexity polynomial in LL, with an exponent fixed before the later correction accuracy. Distinct valid words have constant symbol distance, and a word within a fixed symbol-error radius can be decoded globally in polynomial time.

Begin with the sparse transcript graph of Section 2, whose vertices record partial computations of the predecessor and successor circuits and whose edges change one tape position and its occupation bit. Transcript validity is expressed by bounded-degree polynomial equations in the tape entries. Sampling an individual equation could miss one false equation. Sections 3 and 4 instead encode polynomial remainders recording the equation residuals, and retain certificates for the intermediate products and linear computations that produce them. On exact codewords, a nonzero remainder differs from zero at a constant fraction of positions. The code’s commuting row and column constraints also permit whole-row or whole-column comparisons that give a constant gap for an incorrect certificate identity. All stored components are tested together on one fixed list of neighboring positions, so more certificates enlarge a symbol without diluting the gap.

One tape edit can change all these encoded arrays. Before making an allowed edit, Section 5 prepares each retained array’s finite difference: its value on the edited tape minus its value on the old tape. Certificates introduced by this preparation need their own increments as well. Each new increment has lower assigned polynomial degree in the logical tape entries, so this recursion has bounded depth. Once preparation is complete, adding the increments updates the whole retained tuple to its canonical value on the new tape; the preparation can then be reversed.

The remaining storage issue is the long linear computation needed to prepare an increment. It is carried out one small group of Fourier frequencies at a time: each such orbit is preserved by the encoder and has only polylogarithmically many frequencies. A clock records progress and scratch space is reused. Thus the preparation’s elapsed time lengthens the represented path rather than the data stored at a vertex. The resulting words are the locally evolving RwR_w above.

One fixed binary port. A polynomial-size robust construction applied directly to an NN-bit vertex would not give the required size. Instead we apply it only to the LL-bit outer symbols. The inner construction supplies one injective encoding

D:{0,1}L⟶{0,1}S0,S0=poly⁡(L),Ew=(D(sk))k∈Γ.\mathcal{D}:\{0,1\}^{L}\longrightarrow\{0,1\}^{S_0},\qquad S_0=\operatorname{poly}(L),\qquad E_w=(\mathcal{D}(s_k))_{k\in\Gamma}.

Its encoding and positive correction radius are chosen before the number of symbols inspected by a local function. From that fixed radius, it supports every prescribed fixed average accuracy for requests with bounded address density. More outer correction rounds may enlarge the number of symbols inspected, and hence the number of input ports in the resulting local computation. More inner correction rounds improve its requested bit accuracy. These choices may enlarge constant factors, but they do not change D\mathcal{D} or its radius. All polynomial factors in LL remain fixed powers of log⁡N\log N.

Sections 7–9 construct this port and its robust decision gadget independently of the outer reduction. For a fixed tuple s=(s1,…,sk)s=(s_1,\ldots,s_k) of LL-bit inputs to a Boolean function ff, the inner graph is one computation path with blank work at its source and output f(s)f(s) at its sink. Polynomial charts encode its tapes and certificates. Their dependencies are kept separate for each read-only input, including throughout the finite-difference closure. Consequently the input-dependent parts of the source and its first successor have the same formulas in every later invocation. A one-input template at these two labels defines D(si)\mathcal{D}(s_i) for one input sis_i; its bits then supply the source data for an actual multi-input computation.

The binary representation in Section 8 adds point tables, line tables, and tables for the required products. Correction keeps both addresses in each product request and preserves the required bound on their joint distribution. Its error bound is averaged over requested coordinates; arbitrarily accurate correction at every individual coordinate is neither asserted nor needed. At the inner scale, the geometric construction forces a feedback state near the unique sink, where a positive fraction of encoded coordinates reveal f(s)f(s). These become the many designated outputs of the decision gadget.

From local decisions to an endpoint under gate failures. Section 6 uses the outer tester and correction routines to supply the field’s local information. Two rounded blocks serve as possible vertex encodings. On good validation decisions, each accepted seed has a unique reference vertex; corrected calls supply its incident flags and the requested bits of its own and neighboring encodings. The geometric estimator reserves a bounded list of possible pieces and estimates their statistics before selecting a numerical winner. This order makes average bit accuracy sufficient even when the selected piece depends on the output coordinate.

The generalized circuit has many physical replicas of each geometric coordinate. Write XirX_{ir} for replica rr of component ii, and Xˉi\bar{X}_i for their mean. A fixed-degree expander average AA couples the replicas. Each output is produced by a circuit that realizes the approximate relation

Xir≈clip⁡((AX)ir+βv^ir(Xˉ)),X_{ir} \approx\operatorname{clip}\left((AX)_{ir} + \beta\hat{v}_{ir}(\bar{X})\right),

where v^\hat{v} is the bounded local field estimator. First, boundedness of the update and the expander gap force the replicas close to their means, without assuming that any decision is correct. This synchronization then bounds the number of reads far from their means. Randomized threshold offsets control ambiguous comparisons, and the gate-failure budget controls the circuits containing a failed gate. The randomness describes the sampling analysis: the printed circuit assigns replicas a deterministically enumerated list of fixed tapes of size polynomial in LL.

These charges apply to the complete wired computation. All hypothetical answer branches are allocated before routing, and each physical read occurrence is routed separately with bounded load. Expensive Boolean decision gadgets are shared by groups of output replicas. Their many designated outputs ensure that failures concentrated on extraction wires still spoil only a controlled fraction of the group. On reliable outputs the update approximates the true field; on unreliable outputs whose gates are satisfied, its bounded size still gives an error proportional to β\beta, apart from the numerical gate tolerance. An estimate that keeps clipping inside the replica contraction argument then makes the mean an approximate fixed point. The displacement lower bound forces Xˉ\bar{X} near an endpoint. Rounding its first block and applying the global binary and outer decoders yields the required End-of-Line answer.

The same synchronization, error charging, and clipped-mean argument is used inside the decision gadget. At that scale every output has its own bounded estimator circuit; the additional sharing of decision gadgets occurs only in the outer composition. In both uses, a fixed hypothetical answer branch is analyzed under the original random-tape law, rather than by conditioning on that branch being executed.

Organization and imported inputs. Section 6 assembles the main theorem from the outer representation, the port interface stated there, and the independent geometric interface. It proves universal decoding, the complete binary size bound, and rational-witness totality. Sections 7–9 prove the port interface, and Section 10 proves both the displacement bound and finite numerical access. Section 11 gives the consequences described below. Appendix A collects the separate full-macrograph and unrestricted-product variants; these are not prerequisites for the fixed-port composition.

The outer code uses ternary Goldbach, fixed-generator prime-quotient expansion, and an effective least-prime bound [23, 6, 33]. Its simultaneous systematic encoders, matrix twists, and joint correction guarantees are proved here; a general locally testable code theorem such as [16] does not by itself supply this combination. The inner binary construction uses the corrected scalar line test and two group-theoretic inputs [19, 17, 32]; its vector replacement, affine expansion, and average correction are proved here. The all-modulus Margulis–Gabber–Galil bound supplies the local and replica walks [24]. The inner fields and groups are introduced afresh and are distinct from those of the outer construction.

Consequences for games and markets

Section 11 applies the theorem to the conditional reductions for weak approximate Nash and relative bimatrix Nash [2], course allocation [2], markets with approximately optimal bundles [15], stationary equilibria in discounted games [13, 28, 18], and approximate Hylland–Zeckhauser allocation [7]. For each target we state the precise approximation and encoding conventions before its consequence. The cited reductions provide the transfers to these problems. We supply the needed gate-basis and fan-out conversions, track their fixed error and failure losses, and verify the rational witness and decoder bounds. These consequences use fixed-gap circuit hardness; the quasilinear complete-output bound is the additional assertion of Theorem 1.3.

A sparse macrograph for End-of-Line

References

  1. [1]Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, and Sophus Valentin Willumsgaard. A simple algebraic proof of the PCP theorem. https://arxiv.org/abs/2608.17429v1, 2026. Section 3.1, Definition 3.1 and Claim 3.2.
  2. [2]Yakov Babichenko, Christos H. Papadimitriou, and Aviad Rubinstein. Can almost everybody be almost happy? In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 1–9. ACM, 2016. Full version: Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash, arXiv:1504.02411v4 (2025), Definitions 1 and 4, Conjecture 2, Theorems 2–4, and Appendix B. https://arxiv.org/abs/1504.02411v4.
  3. [3]V. E. Beneš. Permutation groups, complexes, and rearrangeable connecting networks. Bell System Technical Journal, 43(4):1619–1640, July 1964. Lemma 3 and Theorems 2–3. https://doi.org/10.1002/j.1538-7305.1964.tb04102.x.
  4. [4]C. H. Bennett. Logical reversibility of computation. IBM Journal of Research and Development, 17:525–532, November 1973. Reversible cleanup discussion, pp. 525–526. https://doi.org/10.1147/rd.176.0525.
  5. [5]Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences, 47(3):549–595, 1993. Author manuscript, subsection Generic Linear Self-Testing. https://doi.org/10.1016/0022-0000(93)90044-W.
  6. [6]Jean Bourgain and Alex Gamburd. Uniform expansion bounds for Cayley graphs of SL₂(Fₚ). Annals of Mathematics, 167(2):625–642, 2008. Theorem 1 and the discussion on p. 626. https://doi.org/10.4007/annals.2008.167.625.
  7. [7]Mark Braverman, Jingyi Liu, Eric Xue, and Chenghan Zhou. Hardness of approximate Hylland–Zeckhauser equilibria. https://arxiv.org/abs/2606.00951v2, 2026. Version 2, 9 June 2026. Definition 2.1, Table 1, Theorem 3.2, and Lemmas 3.4 and 3.25.
  8. [8]L. E. J. Brouwer. Über Abbildung von Mannigfaltigkeiten. Mathematische Annalen, 71:97–115, 1911. https://doi.org/10.1007/BF01456931.
  9. [9]Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061–1103, 2011. Definition 1 and Theorem 1, p. 1069. Published article.DOI
  10. [10]Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. https://arxiv.org/abs/0704.1678v1, 2007. Version 1. Theorem 1.1, Sections 2 and 4.2, and Lemma 5.6; locators refer to this preprint.
  11. [11]James W. Cooley and John W. Tukey. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation, 19(90):297–301, 1965. Radix-two factorization, pp. 299–300, equations (14)–(22). Article scan.
  12. [12]Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1):195–259, 2009. Section 5.1, Lemmas 5.2–5.5. https://doi.org/10.1137/070699652.
  13. [13]Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang. The complexity of Markov equilibrium in stochastic games. In Proceedings of the Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 4180–4234. PMLR, 2023. Theorem 4, Conjecture 10 and Appendix D use the published numbering. Published article.arxiv.org/abs/2204.03991
  14. [14]Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos. Pure-Circuit: Tight inapproximability for PPAD. Journal of the ACM, 71(5):31:1–31:48, 2024. Numbered references use arXiv:2209.15149v3 (2024), Section 4.1, Definition 3 and Theorem 4.1. https://doi.org/10.1145/3678166.
  15. [15]Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos. Fisher markets with approximately optimal bundles and the need for a PCP theorem for PPAD. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC 2026, pages 1049–1060. Association for Computing Machinery, 2026. Full version, arXiv:2604.27276v2 (18 June 2026), https://arxiv.org/abs/2604.27276v2. Definition 1, footnote 4, Theorem 2.2 and Appendix A are full-version locators; the conference manuscript numbers the equivalence Theorem 2.3.
  16. [16]Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes. Locally testable codes with constant rate, distance, and locality. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 357–374. ACM, 2022. Full version arXiv:2111.04808v2 (2021), Theorems 1.1 and 4.5. https://arxiv.org/abs/2111.04808v2.
  17. [17]Mikhail Ershov and Andrei Jaikin-Zapirain. Property (T) for noncommutative universal lattices. Inventiones Mathematicae, 179(2):303–347, 2010. Numbered references use arXiv:0809.4095v2 (2009): Theorem 1.1 and Section 6.1, equations (6.1)–(6.2), p. 34. https://arxiv.org/abs/0809.4095v2.
  18. [18]Gabriele Farina, Andreas Kontogiannis, Ioannis Panageas, and Vasilis Pollatos. The complexity of computing coarse correlated equilibria in Markov games with a single controller. https://arxiv.org/abs/2607.10897v1, 2026. Version 1. Definition 2.6, Theorem 5.5 and Remark 5.7.
  19. [19]Katalin Friedl and Madhu Sudan. Some improvements to total degree tests. https://arxiv.org/abs/1307.3975v1, 2013. Corrected version, Theorem 13. Original paper in the Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995, pp. 190–198.
  20. [20]O. Gabber and Z. Galil. Explicit constructions of linear-sized superconcentrators. Journal of Computer and System Sciences, 22(3):407–420, 1981. https://doi.org/10.1016/0022-0000(81)90040-4.
  21. [21]Peter Gemmell and Madhu Sudan. Highly resilient correctors for polynomials. Information Processing Letters, 43(4):169–174, 1992. Author manuscript, Appendix A, p. 7, presents the Berlekamp–Welch decoder. https://doi.org/10.1016/0020-0190(92)90195-2.
  22. [22]Noah Golowich. The fine-grained complexity of approximate Nash equilibrium and free games. https://arxiv.org/abs/2609.07136v2, 2026. Version 2, submitted 9 September 2026. Theorem 1.1, Definition 2.1, and Section 2.2.
  23. [23]H. A. Helfgott. The ternary Goldbach conjecture is true. https://arxiv.org/abs/1312.7748v2, 2013. Version 2 (2014), Main Theorem, Section 1.1, p. 2; conclusion in Section 7.4.
  24. [24]Emin Karayel. Expander graphs. Archive of Formal Proofs, March 2023. Isabelle formalization. Theory Expander_Graphs_MGG, function mgg_graph_step and lemma mgg_numerical_radius; normalization in Expander_Graphs_Definition and expansionD2 in Expander_Graphs_Eigenvalues. Online formal development. Accessed September 25, 2026.
  25. [25]G. A. Margulis. Explicit constructions of concentrators. Problemy Peredachi Informatsii, 9(4):71–80, 1973. In Russian; English translation in Problems of Information Transmission 9(4), 325–332. Journal archive.
  26. [26]Abraham Othman, Christos H. Papadimitriou, and Aviad Rubinstein. The complexity of fairness through equilibrium. ACM Transactions on Economics and Computation, 4(4):20:1–20:19, 2016. The Appendix A locator uses arXiv:1312.6249v3 (30 September 2014). Full version.arxiv.org/abs/1312.6249
  27. [27]Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498–532, 1994. https://doi.org/10.1016/S0022-0000(05)80063-7.
  28. [28]Chanwoo Park, Kaiqing Zhang, and Asuman Ozdaglar. Multi-player zero-sum Markov games with networked separable interactions. In Advances in Neural Information Processing Systems, volume 36, 2023. Numbered references use the full version, arXiv:2307.09470v3 (12 July 2025): Definition 1 and Appendix C, Case 1. Full version.arxiv.org/abs/2307.09470
  29. [29]Aviad Rubinstein. Settling the complexity of computing approximate two-player Nash equilibria. In Proceedings of the 57th IEEE Symposium on Foundations of Computer Science, pages 258–265. IEEE, 2016. Numbered references use the full version, arXiv:1606.04550v2 (29 August 2016): Theorem 1.2, Sections 1.1 and 1.3, Lemmas 3.3–3.4, and Sections 5–6. Full version.arxiv.org/abs/1606.04550
  30. [30]Aviad Rubinstein. Inapproximability of Nash equilibrium. SIAM Journal on Computing, 47(3):917–959, 2018. Numbered references use arXiv:1405.3322v5 (2016), Theorem 2, Sections 4–7, and Lemma 5. https://arxiv.org/abs/1405.3322v5.
  31. [31]Steffen Schuldenzucker and Sven Seuken. Monotonic and non-monotonic solution concepts for generalized circuits. https://arxiv.org/abs/1907.12854v1, 2019. Version 1, 30 July 2019. Propositions 1–2, Lemma 1, and Sections 4 and 6.
  32. [32]Yehuda Shalom. Bounded generation and Kazhdan’s property (T). Publications Mathématiques de l’IHÉS, 90:145–168, 1999. Theorem 3.4 and Corollary 3.5, pp. 160–161. https://doi.org/10.1007/BF02698832.
  33. [33]Triantafyllos Xylouris. On Linnik’s constant. https://arxiv.org/abs/0906.2749v1, 2009. Diplomarbeit in German, titled Über die Linniksche Konstante; Theorem 1.1, p. 9.
  34. [34]Gilles Zémor. On expander codes. IEEE Transactions on Information Theory, 47(2):835–837, 2001. Section III-A, Lemma 5 and Theorem 6. https://courses.grainger.illinois.edu/cs598sgt/sp2015/zemor.pdf.DOI

Paper details

vlnc:W_4sppw2e4
Version
v1 · latest
Published
License
LicenseRef-OpenAI-public
Usage

views · 37

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

unreleased internal OpenAI model

View statement
Looking for related papers…
Contents