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 polynomial-time construction of strong thin trees

There is an absolute constant CC such that, given a finite kk-edge-connected loopless multigraph GG on at least one vertex and an integer k≥1k \ge 1, a deterministic algorithm returns a spanning tree TT satisfying ∣δT(S)∣≤Ck∣δG(S)∣|\delta_T(S)| \le \frac{C}{k}|\delta_G(S)| for all ∅≠S⊊V(G)\varnothing \neq S \subsetneq V(G) in time polynomial in the total binary input length, whether edges are listed explicitly or multiplicities are encoded in binary (with the empty tree returned for a one-vertex graph).

For a fixed integer B≥max⁡{1,C}B \ge \max\{1, C\} (where CC is the constant from Theorem 1.1), given a finite undirected graph G=(V,E)G=(V,E) on n≥2n \ge 2 vertices (loops and parallel records allowed) and nonnegative rational numbers xe,cex_e, c_e in binary such that x(δG(S))≥1x(\delta_G(S)) \ge 1 for all ∅≠S⊊V\varnothing \neq S \subsetneq V, there is a deterministic algorithm running in time polynomial in the total binary input length that returns a spanning tree T⊆{e∈E:xe>0}T \subseteq \{e \in E : x_e > 0\} satisfying ∣δT(S)∣≤24B x(δG(S))|\delta_T(S)| \le 24B\, x(\delta_G(S)) for all ∅≠S⊊V\varnothing \neq S \subsetneq V and c(T)≤24B∑e∈Ecexec(T) \le 24B \sum_{e \in E} c_e x_e.

For all sufficiently large integers rr, from an explicit graph HH containing rr disjoint spanning trees one can deterministically construct in polynomial bit time a subgraph H′=(V(H),A)H' = (V(H), A) and an integer r′r' such that r/4≤r′≤r/2r/4 \le r' \le r/2, H′H' contains r′r' disjoint spanning trees, ∣δH′(S)∣≤ar∣δH(S)∣|\delta_{H'}(S)| \le a_r |\delta_H(S)| for every cut with ar=12+3Csr−1/8a_r = \frac{1}{2} + 3C_s r^{-1/8}, and arr′/r≤1+C1r−1/16\frac{a_r}{r'/r} \le 1 + C_1 r^{-1/16} for an absolute constant C1C_1.

There are absolute constants AA and r0r_0 such that if an explicit multigraph HH on at least two vertices contains r≥r0r \ge r_0 edge-disjoint spanning trees, one can deterministically compute a rational X∈KHX \in \mathcal{K}_H and at least (1−Ar−1/16)r(1 - A r^{-1/16})r edge-disjoint spanning trees, every edge ee of which satisfies beTX−1be≤r−1/4b_e^T X^{-1} b_e \le r^{-1/4}, in time and output encoding length polynomial in ∣V(H)∣+∣E(H)∣|V(H)| + |E(H)|.

There is an absolute integer h0h_0 such that, for every integer h≥h0h \ge h_0, every locally hh-connected hierarchy of GG, and every collection M\mathcal{M} of nonroot nodes satisfying ∣O(A)∣≥∣P(A)∣/h|O(A)| \ge |P(A)|/h, there is a matrix D≻0D \succ 0 on E\mathsf{E} with ⟨D,Z⟩≤⟨LG,Z⟩\langle D, Z \rangle \le \langle L_G, Z \rangle for all Z∈NZ \in \mathcal{N} and 1∣O(A)∣∑e∈O(A)beTD−1be≤h−31/40\frac{1}{|O(A)|} \sum_{e \in O(A)} b_e^T D^{-1} b_e \le h^{-31/40} for all A∈MA \in \mathcal{M}.

Suppose BB is the union of qq edge-disjoint spanning trees, where r/2≤q≤rr/2 \le q \le r and rr exceeds an absolute constant. There are vectors ze∈Rn−1z_e \in \mathbb{R}^{n-1}, obtained from faithful reduced incidence columns by one common invertible linear map and positive individual scalings, such that ∑e∈BzezeT=I\sum_{e \in B} z_e z_e^T = I and ∥ze∥2≤1+4/rq\|z_e\|^2 \le \frac{1 + 4/r}{q}, and they admit rational approximations to Euclidean error 2−b2^{-b} in time polynomial in n+∣B∣+r+bn + |B| + r + b.

For an absolute constant CsC_s (specifically Cs=220C_s = 2^{20}), a deterministic polynomial-time procedure finds A⊆BA \subseteq B satisfying ∥∑e∈AweweT−12∑e∈BweweT∥op≤Csr−1/8\|\sum_{e \in A} w_e w_e^T - \frac{1}{2}\sum_{e \in B} w_e w_e^T\|_{\mathrm{op}} \le C_s r^{-1/8}, certified by an exact polynomial-time rational PSD test.

Given rational Hermitian matrices H1,…,HNH_1, \dots, H_N of rank at most one, a deterministic algorithm returns signs σi∈{−1,1}\sigma_i \in \{-1, 1\} such that ∥∑iσiHi∥≤40∥∑iHi2∥1/2\|\sum_i \sigma_i H_i\| \le 40 \|\sum_i H_i^2\|^{1/2} in time polynomial in the total binary encoding length.

Methods

Doubled distance-profile polytope QQ in ℓ∞\ell_\infty with exact radial motion toward cxc_x and cx−c_x^- for transferring bag-selection and shell-charging arguments.

Source excerpts

“Lemma 2.3 (Doubled distance profiles). Every finite metric (S, d) has an isometric realization x 7→ cx in a convex polytope Q in a finite-dimensional normed space with the following properties. Distance ρx(q) = ∥q − cx∥ is affine on Q. There is a common R > 0 and a point c−x ∈ Q such that ∥q − cx∥ + ∥q − c−x ∥ = R (q ∈ Q). (2.7)” · Show in paper

Continuous capacity ramp with convex continuation, partition uncrossing, and an exact minimum-spanning-tree separation oracle for the ellipsoid method.

Source excerpts

“Lemma 3.3 (Partition separation by minimum spanning trees). For nonnegative rational capacities z and rational q ≥ 0, the inequalities z(EH(P)) ≥ q(|P|−1) have an exact polynomial-time separation oracle.” · Show in paper

Log-determinant variational normalization via finite-step rational gradient descent and exact rational LDLTLDL^T elimination to construct a rank-preserving frame.

Source excerpts

“N(d) = X e∈B exp(de)cecTe , f(d) = log det N(d) − 1/q X e∈B de. (4.2)” · Show in paper

Exact rational positive semidefinite decomposition and balanced identity-padding for matrix signing with rational PSD certification.

Source excerpts

“Apply Lemma 5.1 to the rational PSD residual I−Σ, obtaining polynomially many polynomial-bit real rational columns v1, . . . , vJ with V V T = X J j=1 vjvTj = I − Σ, V = [v1 · · · vJ ]. (5.6)” · Show in paper

Finite-bit rational rank-one signing via weak SDP value queries, central-difference derivative approximations, and exact rational elimination for negative-curvature directions.

Source excerpts

“Central first differences, central diagonal second differences, and four-corner mixed second differences of the value oracle, each query to error at most ah2/(128N), give rational approximations gb, b Hb to ∇Ψ, ∇2Ψ” · Show in paper

Binary-multiplicity truncation and rounding reduction to an explicit multigraph of polynomial size.

Source excerpts

“For n ≥ 2, let cuv be the binary multiplicity of the unordered pair uv and set c′uv = min{cuv, k}, auv = ⌊ 2n2 c′uv / k ⌋. (6.6)” · Show in paper