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 Unique Games Theorem

For every fixed ε,δ∈(0,1/2)\varepsilon, \delta \in (0, 1/2), there are an integer s≥1s \ge 1 and a deterministic polynomial-time reduction from 3SAT to explicit unweighted simple bipartite Unique Games instances GφG_\varphi over K=F2sK = \mathbb{F}_2^s with translation constraints a(ve)=a(ue)+cea(v_e) = a(u_e) + c_e such that φ\varphi satisfiable implies val⁡(Gφ)≥1−ε\operatorname{val}(G_\varphi) \ge 1 - \varepsilon and φ\varphi unsatisfiable implies val⁡(Gφ)≤δ\operatorname{val}(G_\varphi) \le \delta, where the alphabet, running-time polynomial degree, and constants depend only on ε,δ\varepsilon, \delta.

For every p∗>0p_* > 0 there is an integer r∗r_* such that for every sufficiently large ℓ\ell, there exist a finite-dimensional binary space V\mathcal{V} containing K=F2ℓK = \mathbb{F}_2^\ell, a map C:V→KC : \mathcal{V} \to K, and a rational probability distribution μ\mu on V\mathcal{V} satisfying C(x+k)=C(x)+kC(x+k) = C(x)+k for k∈Kk \in K, Pr⁡[C(x+a)≠C(x)]≤p∗\Pr[C(x+a) \neq C(x)] \le p_* for uniform x∈Vx \in \mathcal{V} and a∼μa \sim \mu, and Pr⁡a∼μ[∃g∈G,g(a)≠0]≥1/8\Pr_{a \sim \mu}[\exists g \in G, g(a) \neq 0] \ge 1/8 for every linear subspace G≤V∗G \le \mathcal{V}^* with dim⁡(G∣K)≥r∗\dim(G|_K) \ge r_*.

For every η∈(0,1)\eta \in (0, 1) there are α∈(0,1]\alpha \in (0, 1] and integers rs≥1,ℓ0r_s \ge 1, \ell_0 depending only on η\eta such that for every ℓ≥ℓ0\ell \ge \ell_0 and m≥m0(η,ℓ)m \ge m_0(\eta, \ell), any function f:Mat⁡ℓ,m→F2ℓf : \operatorname{Mat}_{\ell,m} \to \mathbb{F}_2^\ell with Pr⁡M,a,l[f(M)=f(M+al⊤)]≥η\Pr_{M,a,l}[f(M) = f(M + al^\top)] \ge \eta satisfies Pr⁡M∣S[f(M)=Mz+u]≥α\Pr_{M|\mathcal{S}}[f(M) = Mz + u] \ge \alpha on some row and column slice S\mathcal{S} with at most rsr_s row and rsr_s column equations.

With latent and shortcode parameters fixed in order, there exist γ>0\gamma > 0 and k0≥8k_0 \ge 8 such that for every cube k≥k0k \ge k_0 and every parity instance, if a folded and shared table family passes the matrix test with probability at least 0.990.99, then the projected advice experiment with β=k−2/3\beta = k^{-2/3} has local strategies with full answer agreement probability at least γ\gamma.

If OPT⁡(E)≤4/5\operatorname{OPT}(\mathcal{E}) \le 4/5, every pair of local randomized strategies in the projected advice experiment satisfies Pr⁡[πˉ(aU)=aO]≤exp⁡(−2−dim⁡W−rs3600k1/3)\Pr[\bar{\pi}(a_U) = a_O] \le \exp\left(-\frac{2^{-\dim W - r_s}}{3600} k^{1/3}\right), which tends to zero uniformly over the parity instance as k→∞k \to \infty along cubes.

For every sufficiently large cube kk, the matrix game G\mathcal{G} constructed from a weighted parity instance E\mathcal{E} with distinct positions satisfies OPT⁡(E)≥1−ξ  ⟹  val⁡(G)≥1−kξ−p∗/2\operatorname{OPT}(\mathcal{E}) \ge 1 - \xi \implies \operatorname{val}(\mathcal{G}) \ge 1 - k\xi - p_*/2 and OPT⁡(E)≤4/5  ⟹  val⁡(G)≤99/100\operatorname{OPT}(\mathcal{E}) \le 4/5 \implies \operatorname{val}(\mathcal{G}) \le 99/100.

Given a finite weighted permutation-constraint game HH with h≥1h \ge 1 occurrences and rational τ>0\tau > 0, one can deterministically construct in polynomial time an unweighted simple bipartite game BB with 4Q4Q edges (Q=⌈h/τ⌉Q = \lceil h/\tau \rceil) and the same alphabet, preserving binary translation constraints, such that ∣val⁡(B)−(1−(1−val⁡(H))/4)∣≤τ/4|\operatorname{val}(B) - (1 - (1 - \operatorname{val}(H))/4)| \le \tau/4.

Let JJ be a fixed Λ\Lambda-instance with A=OPT⁡(J)<B=SDP⁡R(J)A = \operatorname{OPT}(J) < B = \operatorname{SDP}_R(J). For every fixed 0<η<(B−A)/20 < \eta < (B - A)/2, it is NP-hard to distinguish Λ\Lambda-instances II satisfying OPT⁡(I)≥B−η\operatorname{OPT}(I) \ge B - \eta from those satisfying OPT⁡(I)≤A+η\operatorname{OPT}(I) \le A + \eta.

Fix k≥2k \ge 2 and ∅≠Π⊊Sk\emptyset \neq \Pi \subsetneq S_k, and put ρΠ=∣Π∣/k!\rho_\Pi = |\Pi|/k!. For every fixed 0<ε<(1−ρΠ)/20 < \varepsilon < (1 - \rho_\Pi)/2, it is NP-hard to distinguish finite weighted Π\Pi-ordering-CSP instances II satisfying OPT⁡Π(I)≥1−ε\operatorname{OPT}_\Pi(I) \ge 1 - \varepsilon from those satisfying OPT⁡Π(I)≤ρΠ+ε\operatorname{OPT}_\Pi(I) \le \rho_\Pi + \varepsilon, making approximation at every fixed ratio r∈(ρΠ,1]r \in (\rho_\Pi, 1] NP-hard.

For every fixed real constant C>1C > 1, it is NP-hard to approximate Weighted Multicut, nonuniform Sparsest Cut (search task under polynomial-time Cook reductions), weighted Min-2CNF≡\equiv Deletion, and arbitrary weighted-graph Correlation Clustering within factor CC.

Methods

Latent alphabet gadget construction via concatenated quadratic blocks over F2d3\mathbb{F}_{2^d}^3 and enlargement by all binary linear injections B→KB \to K.

Source excerpts

“The fixed-B construction begins with a quadratic block. On an independent uniform input, a uniform nonzero perturbation in one of its update spaces leaves the nonlinear output unchanged with probability θ.” · Show in paper

“Fix ℓ ≥ b + 2 and write K = F ℓ 2 . Let L be the finite set of all binary linear injections L : B → K. Take a product P = ∏ L∈L V0 and define eC((xL)L) = ∑ L∈L L C(xL).” · Show in paper

Outer permutation test using affine tables on kk-tuples of parity equations, exact table keys, and Bellare-Goldreich-Sudan translation folding.

Source excerpts

“We define the key of (Q, P) to be its support together with this entire reduced table. Thus two tables have the same key exactly when their retained coordinates agree, with the same positions, tags, and IDs, and their induced affine maps agree on those coordinates, including their intercepts.” · Show in paper

“We now apply the folding principle of Bellare, Goldreich, and Sudan [7, Section 3.3]: values on one representative determine the values on its translates.” · Show in paper

Matrix extraction via Grassmann-based degree-two shortcode soundness and Fourier decoding in the projected advice experiment with β=k−2/3\beta = k^{-2/3}.

Source excerpts

“Sample U, O, π, then an independent uniform map A : K → F rs 2 and independent uniform maps TO : LO → W, MO : LO → K. Put SO = AMO and send the following inputs to the two provers: U-prover: (U, A, TOπ, S ¯ Oπ¯), O-prover: (O, A, TO, SO).” · Show in paper

“Sample uniform σ ∈ K∗ and form the sign function fσ(N) = (−1)σ(FO(M0+N,TO)), N ∈ X. Sample a Fourier frequency Φ ∈ X∗ with probability | bfσ(Φ)| 2 .” · Show in paper

Clean-coordinate local reconstruction and alphabet-independent projection-game parallel repetition.

Source excerpts

“Call coordinate i clean if it is projected to a singleton and its one advice slope di ∈ EA is zero.” · Show in paper

“These reconstructions define the promised product-game strategies: each side applies its original response rule to the reconstructed input and retains its answers in the slots I, in their original order.” · Show in paper

Largest-remainder weight rounding and 4-edge path subdivision to obtain unweighted simple bipartite translation games.

Source excerpts

“Replace each occurrence e by ne copies, omitting it if ne = 0. The resulting unweighted multigraph H′ has Q occurrences and | val(H′ ) − val(H)| ≤ τ . Orient each occurrence e of H′ from u to v, writing its constraint as av = ρe(au). Replace it by the path u − − pe − − qe − − re − − v, using three fresh interior vertices for every occurrence.” · Show in paper