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

L1 Embeddings of Graphs of Bounded Treewidth

For every integer k≥2k \ge 2, there is a finite constant Ck≥1C_k \ge 1 such that for every finite connected graph G=(V,E)G = (V, E) admitting a tree decomposition with bags of size at most kk and every edge-length function ℓ:E→(0,∞)\ell : E \to (0, \infty), there is a map FF from VV into a finite-dimensional real L1L_1 space satisfying dG,ℓ(u,v)≤∥F(u)−F(v)∥1≤CkdG,ℓ(u,v)d_{G,\ell}(u, v) \le \|F(u) - F(v)\|_1 \le C_k d_{G,\ell}(u, v) for all u,v∈Vu, v \in V, where CkC_k is independent of the number of vertices, the depth of the decomposition, and all ratios of edge lengths.

Let μ\mu be a consistent family of symmetric bag measures with bags of size at most kk. If B0,…,BrB_0, \dots, B_r is a path from a bag containing yy to a bag containing zz, P=BjP = B_j lies on this path, and a labeled cut measure ν\nu on VV satisfies ν∣Bi≤μBi\nu|_{B_i} \le \mu_{B_i} for j≤i≤rj \le i \le r, then the Markov-glued pseudometric satisfies Dμ(y,z)≥bkEν(z∣P)D_\mu(y, z) \ge b_k E_\nu(z \mid P), where bk=C(2k)−1>0b_k = C(2^k)^{-1} > 0.

Any finite schedule requiring at most qq simultaneous reserved particle pairs in each memory copy can be realized using N=2q+k!+2N = 2q + k! + 2 particles and sweep cutoff M=(B(N−1)+2)ΔM = (B(N-1)+2)\Delta, producing consistent symmetric bag measures μt\mu_t of mass 2NM2NM with 2Δ2\Delta sweep margins, Markov-glued pseudometric Dμ(u,v)≤NL(N−1)d(u,v)D_\mu(u, v) \le N L (N-1) d(u, v), and trace domination of any reserved pair along its reservation segment.

After any finite sequence of particle updates starting from zero particles with perturbations satisfying Lip(g)≤L\mathrm{Lip}(g) \le L and sup⁡v∈V∣g(v)∣≤BΔ\sup_{v \in V} |g(v)| \le B\Delta, every particle satisfies Lip(Fi)≤L(N−1)\mathrm{Lip}(F_i) \le L(N-1) and ∣Fi(v)∣≤B(N−1)Δ|F_i(v)| \le B(N-1)\Delta for all 1≤i≤N1 \le i \le N and v∈Vv \in V, regardless of the number of updates.

For every rooted tree decomposition with nonempty bags of size at most kk, there is an L1L_1 pseudometric DbagD_{\mathrm{bag}} on VV and constants Ubag<∞U_{\mathrm{bag}} < \infty and abag>0a_{\mathrm{bag}} > 0, depending only on kk, such that Dbag(u,v)≤Ubagd(u,v)D_{\mathrm{bag}}(u, v) \le U_{\mathrm{bag}} d(u, v) for all u,v∈Vu, v \in V and Dbag(u,v)≥abagd(u,v)D_{\mathrm{bag}}(u, v) \ge a_{\mathrm{bag}} d(u, v) whenever u,vu, v belong to a common bag.

The anchor construction produces an L1L_1 pseudometric DancD_{\mathrm{anc}} on VV satisfying Danc≤UdD_{\mathrm{anc}} \le U d with U=3N(N−1)U = 3N(N-1) depending only on kk.

For each fixed k≥2k \ge 2, there is a constant λk>0\lambda_k > 0 such that for every admissible weighted graph with a tree decomposition of bag size at most kk and every pair of vertices u,vu, v, Dbag(u,v)+Danc(u,v)≥λkd(u,v)D_{\mathrm{bag}}(u, v) + D_{\mathrm{anc}}(u, v) \ge \lambda_k d(u, v).

Methods

Markov gluing of consistent symmetric bag cut laws along a tree decomposition to obtain a global cut measure and L1 pseudometric.

Source excerpts

“Every consistent family of bag measures has a canonical Markov gluing rhomu on OmegaV, of mass m, with trace mut on each bag. It is independent of the chosen root and is symmetric when every bag measure is symmetric.” · Show in paper

Particle list maintenance with affine trace-preserving updates on common weak orders and reservation schedules for freezing particle pairs along bag paths.

Source excerpts

“Let P <= V, and suppose that particles F1, F2 admit a common weak increasing order on P. Put f = (F1 + F2)/2, and let g : V -> R vanish on P. If the four functions F1, F2, f + g, f - g take values in [-M, M], then (sigmaM F1 + sigmaM F2)|P = (sigmaM f+g + sigmaM f-g)|P.” · Show in paper

Co-bag scale-retention schedule launching padded-partition bump perturbations for active dyadic scales.

Source excerpts

“We use the particle construction of Proposition 3.3, reserving one pair of particles for each active scale.” · Show in paper

Deterministic anchor cache with distance-drop eviction thresholds and two-part launch noise combining a random distance multiple with localized dyadic-band bumps.

Source excerpts

“For every ordered pair of distinct vertices p, q in B, consider the two thresholds d(p, q)/100, Jd(p, q). For each threshold tau, protect the entry immediately following a drop from a distance strictly greater than tau to a distance at most tau in the list d(p, A1), d(p, A2), . . . , d(p, Am)” · Show in paper

Nonprincipal ultrafilter compactness argument normalizing a sequence of poorly separated pairs to derive a contradiction via a youngest crossing anchor.

Source excerpts

“We give the limiting argument explicitly. Fix a nonprincipal ultrafilter U on N, obtained by extending the cofinite filter using Zorn's lemma.” · Show in paper