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 Factor-Two Hardness Threshold for Vertex Cover

Minimum Vertex Cover is NP-hard to approximate within every fixed factor α\alpha with 1≤α<21 \le \alpha < 2, even on finite simple undirected unweighted graphs; thus, unless P=NP\mathrm{P} = \mathrm{NP}, no deterministic polynomial-time algorithm achieves factor 2−ε2 - \varepsilon for any fixed ε∈(0,1]\varepsilon \in (0, 1].

For every fixed integer m≥4m \ge 4, there is a deterministic polynomial-time reduction from 3SAT to finite simple undirected unweighted graphs GG such that satisfiable formulas satisfy τ(G)<(12+1m)∣V(G)∣\tau(G) < \left(\frac{1}{2} + \frac{1}{m}\right)|V(G)| and unsatisfiable formulas satisfy τ(G)>(1−1m)∣V(G)∣\tau(G) > \left(1 - \frac{1}{m}\right)|V(G)|, with all vertices and edges listed explicitly.

For a fixed integer m≥4m \ge 4, a fixed even square dd satisfying d≥4d \ge 4 and d>4m\sqrt{d} > 4m, and fixed source alphabets, the graph GG can be output explicitly in deterministic time polynomial in the source bit length, with exact edge tests.

If val(Φ)=1\mathrm{val}(\Phi) = 1, then GG has an independent set of size greater than (1/2−1/m)n(1/2 - 1/m)n, and consequently τ(G)<(1/2+1/m)n\tau(G) < (1/2 + 1/m)n.

For the graph constructed in Section 3, assuming h<dh < d and 16h+32h2≤νd/216h + 32h^2 \le \nu d/2, if val(Φ)≤σ\mathrm{val}(\Phi) \le \sigma, then every independent set has size strictly less than n/mn/m, and consequently τ(G)>(1−1/m)n\tau(G) > (1 - 1/m)n.

Methods

Construct a finite simple undirected unweighted graph GG from a Label Cover instance Φ\Phi by taking vertices v=(c,s)∈[M]E×(Tr)dv = (\mathbf{c}, \mathbf{s}) \in [M]^{\mathcal{E}} \times (\mathcal{T}^r)^d, mapping each vertex to a sum of query-block weight vectors Sv=∑j=1dz(ij(c),sj)S_v = \sum_{j=1}^d z(i_j(\mathbf{c}), s_j), and declaring distinct vertices v,wv, w adjacent when ∥Sv+Sw∥∗≤2t\|S_v + S_w\|_* \le 2t under the compatibility norm ∥z∥∗=max⁡I∈I∣∑(i,λ)∈Izi,λ∣\|z\|_* = \max_{I \in \mathcal{I}} |\sum_{(i,\lambda)\in I} z_{i,\lambda}|.

Source excerpts

“The vertex set consists of all pairs v = (c, s), c ∈ [M]^E, s = (s1, . . . , sd) ∈ (T^r)^d.” · Show in paper

“For two distinct vertices, declare {v, w} ∈ E(G) ⇐⇒ ∥Sv + Sw∥∗ ≤ 2t.” · Show in paper

Convert a large independent set into a fixed odd 11-Lipschitz function F(z)=12(dist∗(z,−A∗)−dist∗(z,A∗))F(z) = \frac{1}{2}(\mathrm{dist}_*(z, -A_*) - \mathrm{dist}_*(z, A_*)) on RP\mathbb{R}^{\mathcal{P}} and evaluate it on fresh independent uniform seeds c\mathbf{c} and continuous uniform weight blocks s∈([−1,1]r)d\mathbf{s} \in ([-1, 1]^r)^d.

Source excerpts

“The function F(z) = 1/2 (dist∗(z, −A∗) − dist∗(z, A∗)) is odd and 1-Lipschitz for ∥·∥∗, and F(z) > t on A∗.” · Show in paper

Use an Efron-Stein product-space orthogonal decomposition over independent seeds and weights, together with a star-resampling operator Dk=∏j≠kO{k,j},jD_k = \prod_{j \ne k} O_{\{k,j\}, j}, to find an hh-element batch JJ and frozen data a\mathbf{a} that retain order-hh variance in own-question conditional means Hj(uj,sj)H_j(u_j, s_j).

Source excerpts

“We use the product-space orthogonal decomposition associated with the Efron–Stein method [7, Section 2], giving the needed projection identities explicitly.” · Show in paper

“Charging the residual components to stars. For each k ∈ [d], define Dk = ∏_{j≠k} Ok,jO_{k,j},j.” · Show in paper

Extract short candidate-label lists Lj(u,s)\mathcal{L}_j(u, s) of size at most ℓ\ell by thresholding the own-question conditional gradients gˉj(u,s)\bar{g}_j(u, s) at β/2\beta/2, and transfer their retained mass to the full gradient rule g∈conv{±vI(i):I∈I}g \in \mathrm{conv}\{\pm v_I(\mathbf{i}) : I \in \mathcal{I}\} via conditional Jensen's inequality.

Source excerpts

“For supported u, define the slot-ordered list Lj(u, s) = {λ ∈ Λij(u)Λ_{ij(u)} : |ḡ_{j,slot_{ij(u)}(λ)}(u, s)| ≥ β/2}.” · Show in paper

“We first transfer the retained mass of the own conditional means to the full gradient rule g, and then apply its pointwise hull bound.” · Show in paper

Decode pairs of positions j<kj < k by fixing all batch weights and all hidden seeds except c{j,k}c_{\{j,k\}}, defining a global Label Cover assignment Aρ,τA_{\rho, \tau} from rank pairs (ρ,τ)∈[ℓ]2(\rho, \tau) \in [\ell]^2 of the own-input lists, and applying the source soundness bound val(Φ)≤σ\mathrm{val}(\Phi) \le \sigma.

Source excerpts

“Fix j < k and write e = {j, k}. Fix all batch weights and all hidden seeds except ce. By independence, the remaining occurrence ce is still uniform on [M].” · Show in paper