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

Constant-factor hardness of directed feedback vertex set

For every fixed real constant A≥1A \ge 1, it is NP-hard to approximate minimum directed feedback vertex set within factor AA on unweighted digraphs, via a deterministic polynomial-time reduction from an NP-hard promise problem to instances (G,k)(G, k) with k∈N>0k \in \mathbb{N}_{>0} such that DFVS(G)≤k\mathrm{DFVS}(G) \le k in the YES case and DFVS(G)>Ak\mathrm{DFVS}(G) > Ak in the NO case.

For every fixed real A≥1A \ge 1, approximating directed feedback arc set within factor AA is NP-hard on unweighted simple loopless digraphs, via a deterministic polynomial reduction producing a digraph HH and a positive integer kk with DFAS(H)≤k\mathrm{DFAS}(H) \le k in the YES case and DFAS(H)>Ak\mathrm{DFAS}(H) > Ak in the NO case.

If the input two-to-one game has a labeling satisfying a fraction at least 1−θ1 - \theta of its constraints under ν\nu, then the constructed weighted digraph has a feedback vertex set of cost at most 44.

For each fixed AA, the weighted reduction produces a loopless digraph with positive rational vertex costs in deterministic polynomial time in the game input size, with vertex costs bounded above by a constant CAC_A depending only on AA.

If the input two-to-one game has value at most θ\theta, every feedback vertex set of the constructed weighted digraph has cost strictly greater than D=10AD = 10A.

Rounding and cloning converts a loopless digraph GG on S≥1S \ge 1 vertices with positive rational vertex costs wv≤Cw_v \le C into an unweighted digraph G^\widehat{G} on at most CS2+SCS^2 + S vertices in deterministic polynomial time for fixed CC, such that a feedback vertex set of GG of cost at most aa yields a feedback vertex set of G^\widehat{G} of size at most S(a+1)S(a+1), and if every feedback vertex set of GG has cost greater than bb, then DFVS(G^)>Sb\mathrm{DFVS}(\widehat{G}) > Sb.

For p=2−kp = 2^{-k} with integer k≥1k \ge 1, every b≥0b \ge 0, and every α>0\alpha > 0, there is a finite integer J(p,b,α)J(p, b, \alpha) independent of ∣S∣|S| such that every Boolean function f:2S→{0,1}f : 2^S \to \{0, 1\} with Ip(f)≤bI_p(f) \le b has a Boolean junta approximant on at most J(p,b,α)J(p, b, \alpha) coordinates with error at most α\alpha under μpS\mu_p^S.

For every integer L≥3L \ge 3 and every η>0\eta > 0, there are an integer N≥LN \ge L and a rational probability distribution on increasing maps ψ:[L]↪[N]\psi : [L] \hookrightarrow [N] such that TV(L(ψ(I)),L(ψ(I′)))≤η\mathrm{TV}(\mathcal{L}(\psi(I)), \mathcal{L}(\psi(I'))) \le \eta for all I,I′∈([L]3)I, I' \in \binom{[L]}{3}.

Methods

Dyadic-to-uniform junta reduction: reducing a Boolean function at dyadic bias p=2−kp = 2^{-k} to a function on k∣S∣k|S| uniform bits via Zj=⋀a=1kXj,aZ_j = \bigwedge_{a=1}^k X_{j,a} and taking the optimal conditional predictor on revealed blocks.

Source excerpts

“Let (Xj,a)j∈S, a∈[k] be independent uniform bits and put Zj = ∧ka=1 Xj,a, F(X) = f({j ∈ S : Zj = 1}). ... Reveal all bits in every block indexed by J. Since H is measurable with respect to these revealed blocks, the Boolean predictor with smallest conditional error from the revealed blocks has total error at most that of H.” · Show in paper

Rank-spreading distribution construction: constructing a rational probability distribution on increasing embeddings ψ:[L]↪[N]\psi : [L] \hookrightarrow [N] with η\eta-indistinguishable triple marginals via a finite zero-sum game, finite Ramsey theory for triples, and the finite minimax theorem.

Source excerpts

“The finite Ramsey theorem for triples [11, Theorem B] gives an N such that every coloring of ([N]3) with at most b|I|2 colors has a monochromatic set of size L. Consider the following finite zero-sum game. ... By the finite minimax theorem [14, Section II.3], there is a probability distribution µ on increasing maps for which the expected payoff against every pure test is at most δ.” · Show in paper

Shared-prefix conditioning and permutation pivotality budget: partitioning label tuples by successive random subsets to define monotone conditioned functions across all dyadic scales simultaneously, and bounding their total influence and acceptance probability via a single-label permutation pivotality budget B(f)B(f).

Source excerpts

“Successive random subsets split label tuples into lexicographically ordered cells. Monotonicity selects a unique transition cell, and prefix identifications make these transitions consistent under refinement. ... The resulting quantity B(f) is the sum, over labels, of the probability that the label is pivotal at some prefix of a random permutation of the other labels. It bounds both total influence and acceptance probability divided by the bias, at every bias.” · Show in paper

Cost-removal via vertex-count-scaled rounding and cloning: converting positive rational vertex costs wv≤Cw_v \le C on an SS-vertex loopless digraph to unweighted vertices by setting cv=⌈Swv⌉c_v = \lceil S w_v \rceil and replacing each vertex vv by an independent set Cv\mathcal{C}_v of cvc_v unweighted vertices.

Source excerpts

“Let G be a loopless digraph on S ≥ 1 vertices with positive rational vertex costs wv ≤ C. Set cv = ⌈Swv⌉. Replace every vertex v by an independent set Cv of cv unweighted vertices, and replace every arc u → v by all arcs from Cu to Cv.” · Show in paper