By OpenAISourceGitHub

Manuscripts from openai/math

Fork
Clone
git clone https://openversions.com/git/index/openai-math.git
Cite
Version link
https://openversions.com/index/openai-math/commit/dfd8c46870b48511e697cbb43a3c8c91d375fa2f
Version identifier (commit hash)
dfd8c46870b48511e697cbb43a3c8c91d375fa2f

Fork to create your own copy with credit to the source. Clone to get a Git copy on your computer.

All papers

Claims

Findings

The PCP-for-PPAD conjecture: a quasilinear reduction

There are fixed rational constants 0<ε<1/100 < \varepsilon < 1/10 and 0<δ<10 < \delta < 1, a fixed positive integer AA, a fixed nonnegative integer bb, a fixed polynomial pp with nonnegative integer coefficients, and deterministic polynomial-time algorithms R,DR, D such that: (i) every generalized circuit 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, R(I)R(I) is a generalized circuit of complete encoding length M≤AN⌈log⁡2(N+2)⌉bM \leq A N \lceil \log_2(N+2) \rceil^b; (iii) RR runs in time polynomial in NN; and (iv) for every acceptable assignment xx of R(I)R(I), D(I,x)D(I,x) returns a solution of II in time polynomial in NN plus the encoding length of xx.

For every End-of-Line input of length NN, uniform deterministic polynomial-time algorithms construct a directed graph of valid extended labels with indegree and outdegree at most one, no isolated vertices, a public source, and canonical words Rv∈({0,1}L)ΓR_v \in (\{0,1\}^L)^\Gamma with ∣Γ∣=Npoly⁡(ℓN)|\Gamma| = N \operatorname{poly}(\ell_N) and L=(ℓN+Cbase)CLL = (\ell_N + C_{\text{base}})^{C_L} admitting constant distance, a bounded-query local tester, local proposals/flags, value-independent uncertainty correction, and polynomial-time global recovery.

For every fixed positive integer exponent allowance callowc_{\text{allow}}, there are a cutoff LportL_{\text{port}} and a uniform family of injective binary encodings D:{0,1}L→{0,1}S0\mathcal{D} : \{0,1\}^L \to \{0,1\}^{S_0} (S0=poly⁡(L)S_0 = \operatorname{poly}(L)) with fixed positive relative distance dBd_B, degree-at-most-10 multilinear coordinates over F2\mathbb{F}_2, a perfect-completeness bounded-query tester, and—for any fixed arity kk, size factor CfC_f, and output loss υ>0\upsilon > 0—a uniform generalized subcircuit for any single-bit Boolean function of size at most CfLcallowC_f L^{c_{\text{allow}}} that tolerates δgG0\delta_g G_0 failed gates and γgG0\gamma_g G_0 spoiled external comparisons.

For any finite directed graph of indegree and outdegree at most one with no self-edges or isolated vertices and d∗d_*-separated binary vertex encodings, there is a union L⊂[−1,2]4m\mathcal{L} \subset [-1,2]^{4m} of directed, rounded paths and cycles with desired endpoint set E\mathcal{E} and a displacement field v:B→R4mv : \mathcal{B} \to \mathbb{R}^{4m} satisfying ∥v(X)∥∞≤B1−1\|v(X)\|_\infty \leq B_1 - 1 and ∥clip⁡B(X+βv(X))−X∥≥c∗β\|\operatorname{clip}_{\mathcal{B}}(X + \beta v(X)) - X\| \geq c_* \beta whenever dist⁡(X,E)>10τ\operatorname{dist}(X, \mathcal{E}) > 10\tau and 0<β≤β00 < \beta \leq \beta_0, along with a finite local numerical schema v^I(X)\widehat{v}_I(X) achieving 4EI,trial∣v^I(X)−vI(X)∣2≤a24\mathbb{E}_{I,\text{trial}}|\widehat{v}_I(X) - v_I(X)|^2 \leq a^2 under admissible local access.

There are fixed positive rational constants εw,δw\varepsilon_{\text{w}}, \delta_{\text{w}} and a fixed polynomial pwp_{\text{w}} such that finding a rational product mixed-strategy profile σ\sigma of total encoding length at most pw(L)p_{\text{w}}(L) with ∣{i:reg⁡i(σ)>εw}∣≤⌊δwn⌋|\{i : \operatorname{reg}_i(\sigma) > \varepsilon_{\text{w}}\}| \leq \lfloor \delta_{\text{w}} n \rfloor in an explicitly encoded rational two-action polymatrix game of maximum degree at most three is PPAD-hard under deterministic polynomial-time many-one search reductions.

There are a fixed rational 0<εr<10 < \varepsilon_{\text{r}} < 1 and a fixed polynomial prp_{\text{r}} such that finding a rational mixed-strategy profile of total encoding length at most pr(L)p_{\text{r}}(L) satisfying relative εr\varepsilon_{\text{r}}-approximate Nash equilibrium conditions in an explicitly encoded rational bimatrix game (A,B)(A, B) with A≥0A \geq 0 and B≤0B \leq 0 is PPAD-complete under deterministic polynomial-time many-one search reductions.

There are a fixed rational 0<γc<1/20 < \gamma_{\text{c}} < 1/2 and a fixed polynomial pcp_{\text{c}} such that finding rational prices and positive rational budgets with demanded bundles of total encoding length at most pc(L)p_{\text{c}}(L) satisfying ∥z∥2≤α∗\|z\|_2 \leq \alpha_* and Gini⁡(b)≤γc\operatorname{Gini}(b) \leq \gamma_{\text{c}} in indivisible course allocation is PPAD-complete under deterministic polynomial-time many-one search reductions.

For every fixed 0<εm<1/90 < \varepsilon_{\text{m}} < 1/9, there is a fixed rational 0<δm<10 < \delta_{\text{m}} < 1 such that finding an (εm,δm)(\varepsilon_{\text{m}}, \delta_{\text{m}})-approximate equilibrium in simple Fisher markets (and their exchange-market versions with identical endowments and strongly connected economies) is PPAD-hard under deterministic polynomial-time many-one search reductions.

For some fixed rational εs>0\varepsilon_{\text{s}} > 0, finding an εs\varepsilon_{\text{s}}-stationary Markov CCE (or Nash equilibrium) in two-player turn-based general-sum discounted games with discount γ=1/2\gamma = 1/2, rewards in [−1,1][-1,1], and at most two actions per state is PPAD-hard under deterministic polynomial-time many-one search reductions.

Finding an ε△\varepsilon_\triangle-stationary Markov CCE in rational three-player zero-sum K3K_3-separable games (discount 1/21/2) and finding an εsc\varepsilon_{\text{sc}}-stationary Markov CCE in rational two-player single-controller games (discount γ∈[1/16,1)\gamma \in [1/16, 1)) are PPAD-hard under deterministic polynomial-time many-one search reductions.

There are a fixed rational εh>0\varepsilon_{\text{h}} > 0 and a fixed polynomial php_{\text{h}} such that finding an εh\varepsilon_{\text{h}}-Hylland–Zeckhauser equilibrium with rational prices and allocation of total encoding length at most ph(L)p_{\text{h}}(L) is PPAD-hard under deterministic polynomial-time many-one search reductions.

Methods

Sparse macrograph and cyclic four-phase schedule for End-of-Line with reciprocal forward/reverse proposals and bounded-arity local validity tests.

Source excerpts

“The schedule uses four phases. To see their effect when all computations succeed, suppose Qx and Qy exist and y = S(x). Starting with A = Qx and B empty, it fills B with Qy, erases A by reversing reconstruction from y, copies B into A, and erases B.” · Show in paper

Outer index group Γ=F2r⋊H\Gamma = \mathbb{F}_2^r \rtimes H with H=∏a=13PGL⁡2(Fpa)H = \prod_{a=1}^3 \operatorname{PGL}_2(\mathbb{F}_{p_a}) constructed via ternary Goldbach, paired with simultaneous systematic square codes and matrix twists.

Source excerpts

“Helfgott’s ternary Goldbach theorem says that every odd integer greater than five is a sum of three primes [23, Main Theorem]. For our even r we can therefore find primes p1, p2, p3 with r − 3 = p1 + p2 + p3, by exhaustive search in [r].” · Show in paper

Mode-serial reversible filling of full slots using Fourier frequency cutoffs PτP_\tau that commute with the systematic encoder, combined with two-buffer reversible cleanup.

Source excerpts

“Retaining the completed target while reversing its auxiliary computation follows the reversible-cleanup principle of Bennett [4, pp. 525–526]. The two-buffer schedule, local transitions, and certification guarantees needed here are established in the following proof.” · Show in paper

Finite-difference closure of persistent certificates and verification auxiliaries in bounded logical-degree tiers for local tape evolution.

Source excerpts

“Lemma 5.1 (Closure under finite differences). For every positive-degree persistent full slot D and every σ ∈ Σ, one can allocate a finite certified full program whose output, in the same encoder type as D, is the increment of D under b → b + hσ(c).” · Show in paper

Expander-coupled physical replica synchronization using the Margulis–Gabber–Galil operator and a clipped-mean contraction argument.

Source excerpts

“For each i, average the replica labels using the half-lazy Margulis–Gabber–Galil operator Arep on (Z/qZ)2, q = √R.” · Show in paper

Inner algebraic representation with lifted cyclic interpolation, smooth linear verification via division by Xjh−XjX_j^h - X_j, and projection stacks using full-label dilations.

Source excerpts

“Instead we express each restriction as a sum of invertible affine pullbacks and store the affine-pulled values in slots. The progress coordinate t specifies which of these slots are active.” · Show in paper

Rectangular coordinates with transitive affine-group action, systematic row extension, and value-independent uncertainty support contraction for binary blocks.

Source excerpts

“The rectangular coordinates below make this action transitive on point and ordered-line columns. Target affine maps commute with it, so neighbor updates remain column permutations after row encoding.” · Show in paper