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

Perfect completeness for 2-to-1 games

For every fixed rational δ∈(0,1)\delta \in (0, 1), there are an integer q=q(δ)≥2q = q(\delta) \ge 2 and a deterministic polynomial-time reduction from 3-SAT to 2-to-1 games with alphabets [2q][2q] and [q][q] such that a satisfiable formula produces a game of value 11, and an unsatisfiable formula produces a game of value at most δ\delta, with an explicit nonempty list of unweighted edge occurrences and an explicit table for every projection map.

There are absolute constants C>0C > 0 and an integer k0≥3k_0 \ge 3 such that, for every fixed integer k≥k0k \ge k_0, it is NP-hard to distinguish a kk-colorable finite unweighted graph G=(W,F)G = (W, F) with F≠∅F \neq \emptyset from one in which every coloring χ:W→[k]\chi : W \to [k] satisfies ∣{{u,v}∈F:χ(u)≠χ(v)}∣/∣F∣≤1−1k+Clog⁡kk2|\{\{u, v\} \in F : \chi(u) \neq \chi(v)\}| / |F| \le 1 - \frac{1}{k} + C \frac{\log k}{k^2}.

For every fixed 0<ε<3/80 < \varepsilon < 3/8, it is NP-hard to distinguish a satisfiable instance with constraints NTW(ℓ1,ℓ2,ℓ3)\mathrm{NTW}(\ell_1, \ell_2, \ell_3) from one in which every assignment satisfies at most a 5/8+ε5/8 + \varepsilon fraction of the constraints; consequently, every language in NP has a polynomial-time verifier using O(log⁡n)O(\log n) random bits and three nonadaptive proof-bit queries, with perfect completeness and soundness at most 5/8+ε5/8 + \varepsilon.

With the fixed parameters of Section 8, the preliminary legal-answer game has perfect completeness, fibers of size at most two, and value less than ε\varepsilon on every unsatisfiable source instance.

Under the hypotheses of Proposition 5.4, for the pair i<ji < j supplied by pair counting, there are randomized strategies measurable on the left and right local inputs returning bilinear forms FLF_L on HiH_i and FRF_R on Hi′H'_i such that Pi(FR=FL∣Hi′×Hi′)≥γj>0\mathbb{P}_i(F_R = F_L|_{H'_i \times H'_i}) \ge \gamma_j > 0, where γj\gamma_j depends only on c,α,r,ℓjc, \alpha, r, \ell_j and is independent of ℓi\ell_i, branching numbers, source alphabet, and instance size.

Under the hypotheses of Proposition 6.3, the original randomized decoders satisfy Pr⁡[FL∣Hi′×Hi′=FR,  FL is admissible at S,  rank FL≤s]≥γ/2\Pr[F_L|_{H'_i \times H'_i} = F_R, \; F_L \text{ is admissible at } S, \; \mathrm{rank}\, F_L \le s] \ge \gamma/2 in the modified experiment.

Assuming val(Gsrc)<1/(2s2)\mathrm{val}(G_{\mathrm{src}}) < 1/(2s^2), the event Li,j,s\mathcal{L}_{i,j,s} in the modified experiment that the two original decoder outputs agree on Hi′H'_i while the left output is a normalized product form on HiH_i of full rank at most ss satisfies Pr⁡(Li,j,s)≤(1−βip0,i64)ni≤exp⁡(−p0,i64ni1/3)\Pr(\mathcal{L}_{i,j,s}) \le (1 - \frac{\beta_i p_{0,i}}{64})^{n_i} \le \exp(-\frac{p_{0,i}}{64} n_i^{1/3}).

Methods

Construct a tree of pointwise function spaces HD(Q)=∑C child of DHC(Q)2H_D(Q) = \sum_{C \text{ child of } D} H_C(Q)^2 over F2\mathbb{F}_2 and canonicalize joint-evaluation functions into unordered fiber partitions Pf\mathcal{P}_f with typed reduced-domain coordinates, discarding unused slots and uniquely reducible clause slots.

Source excerpts

“Definition 3.1 (Pointwise function spaces). For any such tuple Q of clause and variable questions, define finite vector spaces over F2 recursively. At a leaf C, set HC(Q) = F_2^{\Omega_C(Q)}, the space of all functions from its answer domain to F2. For every node C, set HC(Q)^2 = span{gh : g, h ∈ HC(Q)}, (gh)(x) = g(x)h(x). At a nonleaf node D, put HD(Q) = \sum_{C child of D} HC(Q)^2 ⊆ F_2^{\Omega_D(Q)}.” · Show in paper

“Let Pf = {ef^{-1}(y) : y ∈ im f} (3.6) be the unordered partition of this reduced domain into nonempty fibers. The canonical key kL(f) consists of a left-side tag, the retained typed coordinates, and Pf.” · Show in paper

Sample arrays along a random root-to-leaf path using a recursive-product sampler with fresh random tapes for every call, and form one-bit constraints by quotienting one nonleaf block by a random nonzero direction.

Source excerpts

“Every invocation of Sample uses a new random tape for the entire recursive call tree. In particular the two factors in one product, the factors in different products, and calls made on behalf of different displayed arrays are independent conditional on E, P.” · Show in paper

Analyze cut-level distributions via a stopped-call representation, a one-hidden-child total-variation comparison, and a sparse-projection comparison with an adaptive-witness posterior bound.

Source excerpts

“Lemma 4.1 (Stopped-call representation). Fix E and the path from the root through Dp, including Dp but no choice of its child. The original sampling can be generated as follows. First generate an exterior record Ξp consisting of the random choices outside Dp's subtree, with every recursive call reaching Dp left unevaluated. Then generate the pending scalar calls at Dp, its own buckets, and the arrays strictly below Dp.” · Show in paper

“Lemma 4.4 (Posterior bound for adaptive witnesses). In Mi, condition on E, the path through Di and a permissible exterior record. Let X = (XC)C consist of all lifted raw child blocks, including any fixed number of independent uniform cut rows.” · Show in paper

Decode upper-level responses into bilinear forms using a finite-range partial-table inverse theorem with dummy-column elimination and heavy-character lists under a small-bias hidden-bucket law.

Source excerpts

“Theorem 2.6 (Inverse theorem for a finite-range partial table). For every 0 < η < 1, there are α > 0, integers r ≥ 1 and ℓ0, depending only on η, with the following property.” · Show in paper

“Lemma 5.3 (One heavy list for all affine-slice witnesses). Let K = F_2^\ell, let W ⊆ K have codimension at most r, and let H′ be a finite vector space. Let µ be a probability law on V = W ⊗ H′ with |EµχΦ| ≤ λ for every nonzero Φ ∈ V∗.” · Show in paper

Transfer tested-rank agreement to full-rank agreement by resampling within the lower omitted-direction fiber and refuting dense high-rank forms on affine row/column slices.

Source excerpts

“Lemma 6.1 (Resampling and transfer to full equality). Fix complete local tapes and the left erasure just described. Suppose the nonerased left form agrees with the right form on H′ i ×H′ i with probability h in the modified experiment.” · Show in paper

“Lemma 6.2 (Fixed forms on affine row/column slices). Let H be a finite-dimensional vector space over F2, let F be a bilinear form on H, and let ℓ, r′, m be nonnegative integers with m ≥ 1 and ℓ ≥ 2m + r′.” · Show in paper

Extract odd-size legal answer lists from normalized low-rank bilinear forms via leaf indicators and apply parallel repetition on clean projected children whose sampled contributions vanish.

Source excerpts

“Lemma 7.1 (Odd-list projection and extraction). Every map in Equation (7.1) sends Os(Λ) into Os(Γ). In particular, Godd,s is a total projection game, and val(Godd,s) ≤ s^2 val(Gsrc).” · Show in paper

“Lemma 7.2 (Exact clean probability and conditional source law). Conditional on any exterior datum Ξ = ξ of positive probability, the clean indicators are independent.” · Show in paper