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

A Direct Proof of Optimal Max-Cut Hardness

For every fixed α\alpha with αGW<α≤1\alpha_{\mathrm{GW}} < \alpha \le 1, it is NP-hard to approximate Max-Cut within a factor of α\alpha on simple unweighted graphs.

For any fixed rational t∈(0,1)t \in (0, 1) and constant 0<ε<(t−B(t))/40 < \varepsilon < (t - B(t))/4 where B(t)=2πarcsin⁡tB(t) = \frac{2}{\pi}\arcsin t, it is NP-hard on graphs equipped with a rational probability distribution on edges to distinguish Val≥1+t2−ε\mathrm{Val} \ge \frac{1+t}{2} - \varepsilon from Val≤1+B(t)2+ε\mathrm{Val} \le \frac{1+B(t)}{2} + \varepsilon.

For every constant b∈(0,1)b \in (0, 1), there is an integer n≥1n \ge 1 depending only on bb such that for every constant a∈(0,1−b)a \in (0, 1-b), it is NP-hard to distinguish bipartite projection games with vertex label sets F2n+1,F2n\mathbb{F}_2^{n+1}, \mathbb{F}_2^n and surjective affine projections πe:F2n+1→F2n\pi_e : \mathbb{F}_2^{n+1} \to \mathbb{F}_2^n of value ≥1−a\ge 1-a from those of value ≤b\le b, via a deterministic polynomial-time reduction.

For the tree code W(R,F)W(R, F) with complementary slice D\mathcal{D} and tt-coupled slice tables F,F′F, F' and rr-retained rows R1,R2R^1, R^2, every a∈Aa \in \mathcal{A} and every fixed slice D\mathcal{D} satisfy E[W(R1,F)(a)W(R2,F′)(a)∣D]=tr2d\mathbb{E}[W(R^1, F)(a)W(R^2, F')(a) \mid \mathcal{D}] = t r^{2d}, and negating all tables on a slice negates WW.

For any finite-dimensional F2\mathbb{F}_2-vector space HH, real Hilbert space V\mathcal{V}, and vectors c(q,z)∈Vc(q, z) \in \mathcal{V} with wq=∑z∈F2s∥c(q,z)∥2w_q = \sum_{z \in \mathbb{F}_2^s} \|c(q,z)\|^2 and M=∑q∈H∗wqM = \sum_{q \in H^*} w_q, the random hash U(z)=∑q∈H∗χq(L)c(q,z+J(q))U(z) = \sum_{q \in H^*} \chi_q(L) c(q, z + \mathbf{J}(q)) satisfies E∑z∥U(z)∥2=M\mathbb{E} \sum_z \|U(z)\|^2 = M, and for every ζ>0\zeta > 0 there exist γ>0,s0∈N\gamma > 0, s_0 \in \mathbb{N} depending only on ζ\zeta such that for s≥s0s \ge s_0, max⁡qwq≤γM  ⟹  Emax⁡z∥U(z)∥2≤ζM\max_q w_q \le \gamma M \implies \mathbb{E} \max_z \|U(z)\|^2 \le \zeta M.

For fixed t∈(0,1)t \in (0, 1), 0<δ<1−B(t)0 < \delta < 1 - B(t), and 0<μ<1/20 < \mu < 1/2, there exist tree parameters s≥2,m≥1s \ge 2, m \ge 1 and constants p∗,θ>0p_*, \theta > 0 depending only on t,δ,μt, \delta, \mu such that for any affine label space A\mathcal{A} and any odd family ϕω:{−1,1}A→[−1,1]\phi_\omega : \{-1,1\}^{\mathcal{A}} \to [-1,1], if Eω,D,R,FoutStabtFD(fˉω)≥B(t)+δ\mathbb{E}_{\omega, \mathcal{D}, R, F_{\mathrm{out}}} \mathrm{Stab}_t^{F_{\mathcal{D}}}(\bar{f}_\omega) \ge B(t) + \delta, then Pr⁡[max⁡q∈Amq(fˉω;Γ,Fout)≥θ]≥p∗\Pr[\max_{q \in \mathcal{A}} m_q(\bar{f}_\omega; \Gamma, F_{\mathrm{out}}) \ge \theta] \ge p_*.

If the extraction conclusion of Proposition 7.1 holds with constants p∗,θ>0p_*, \theta > 0 and T≥1p0(p∗θ)2T \ge \frac{1}{p_0 (p_* \theta)^2} where p0=2−n(2k−2s)p_0 = 2^{-n(2k-2s)}, then the original affine game has value Val(G)≥2−2sp∗θ2\mathrm{Val}(\mathcal{G}) \ge 2^{-2s} \frac{p_* \theta}{2}.

For any graph GG on NN vertices with nonnegative rational weights wuvw_{uv} on unordered distinct pairs summing to at most 11 and any fixed ϵ′>0\epsilon' > 0, one can construct in deterministic polynomial time a simple unweighted graph G′G' and an integer scale QQ such that ∣MaxCut(G′)Q−MaxCut(G)∣≤ϵ′|\frac{\mathrm{MaxCut}(G')}{Q} - \mathrm{MaxCut}(G)| \le \epsilon' (and likewise after deleting loops).

Methods

Tree code with complementary traversals: a complete rooted 2s2s-ary tree of depth mm with Boolean gate tables Fv:F2s→{−1,1}F_v : \mathbb{F}_2^s \to \{-1,1\} and leaf affine rows Ri∈HR_i \in H, where a random slice D\mathcal{D} selects both children of one pair at each depth above J0J_0 so that every Walsh monomial traversal meets D\mathcal{D} at exactly one node.

Source excerpts

“Definition 3.1 (Tree code). Fix integers s ≥ 2 and m ≥ 1, and put k = (2s)^m, d = s^m. Let T be the complete rooted 2s-ary tree of depth m. The children of each internal node v are indexed by (g, b) ∈ [s] × {0, 1}. Its leaves are indexed by [k]. To each internal node assign a table Fv : F_2^s → {−1, 1}, and to each leaf assign a row Ri ∈ H.” · Show in paper

Long-code Max-Cut test: for each TT-tuple of left vertices x‾∈XT\underline{x} \in X^T, vertices are (x‾,w)(\underline{x}, w) for w∈{−1,1}Bw \in \{-1,1\}^{\mathcal{B}}; edges are sampled by drawing y‾∈YT\underline{y} \in Y^T, two independent conditional edge tuples e‾,e‾′\underline{e}, \underline{e}', a random slice D\mathcal{D} with tt-coupled tables F,F′F, F' on D\mathcal{D}, and rr-retained rows R1,R2R^1, R^2, outputting (x‾,W(R1,F)∘πe‾)(\underline{x}, W(R^1, F) \circ \pi_{\underline{e}}) and (x‾′,−W(R2,F′)∘πe‾′)(\underline{x}', -W(R^2, F') \circ \pi_{\underline{e}'}).

Source excerpts

“Output the unordered edge whose endpoints are (x, W(R1, F) ◦ πe), (x', −W(R2, F') ◦ πe').” · Show in paper

Decoding with a hidden planted coordinate: repeating the affine game TT times and planting zero linear coefficients in one uniformly chosen slot a∗∈[T]a_* \in [T] across all context and latent rows so that the XX-labeler can lift the context without knowing the incident edge projection πe\pi_e.

Source excerpts

“The planted experiment chooses a uniform mark a∗ ∈ [T] and sets these blocks to zero at a∗. All other row coefficients, the noise masks, the outside tables, and the game edges retain their original distributions.” · Show in paper

Deterministic conversion of weighted graphs with loops to simple unweighted graphs by replacing each vertex with a cluster Fp6\mathbb{F}_p^6 and connecting xx in cluster uu to yy in cluster vv iff x⋅y∈Iuvx \cdot y \in I_{uv} for ⌊pwuv⌋\lfloor p w_{uv} \rfloor residues.

Source excerpts

“Replace every vertex by a cluster indexed by F_p^6. For each u < v let Iuv ⊆ Fp be any fixed set of ⌊pwuv⌋ residues, for example the first such residues in the usual ordering. Join x in cluster u to y in cluster v exactly when x · y ∈ Iuv.” · Show in paper