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

Integral and fractional expectation thresholds are equivalent

For every finite nonempty set XX and every nonempty proper increasing family F⊆2X\mathcal{F} \subseteq 2^X, qf(F)≤25⋅5124q(F)q_f(\mathcal{F}) \le 25 \cdot 512^4 q(\mathcal{F}), with both thresholds using the covering budget 1/21/2 and the constant independent of ∣X∣|X|, the sizes of the minimal members of F\mathcal{F}, and the support of the fractional cover.

If XX is a finite set, F\mathcal{F} is a nonempty family of nonempty subsets of XX that is not pp-small (0<p≤10 < p \le 1), λH\lambda_H is a probability mass function supported on HH for each H∈FH \in \mathcal{F}, D=256D = 256, and s≥0s \ge 0 is an integer with p∑i=1sDi≤1/2p \sum_{i=1}^s D^i \le 1/2, then under independent vertex coloring a:X→{1,…,s+1}a: X \to \{1, \dots, s+1\} with πi=Dip\pi_i = D^i p (1≤i≤s1 \le i \le s) and πs+1=1−p∑i=1sDi\pi_{s+1} = 1 - p \sum_{i=1}^s D^i, with probability at least 9/109/10 there is an H∈FH \in \mathcal{F} such that λH(Ai(a))≥1−2−i\lambda_H(A_i(a)) \ge 1 - 2^{-i} for all 1≤i≤s1 \le i \le s, and in particular ∑x∈Xa(x)λH(x)≤2\sum_{x \in X} a(x) \lambda_H(x) \le 2.

For a probability mass function λ\lambda on a finite set XX, A⊆XA \subseteq X, m≥0m \ge 0, and 0<d<10 < d < 1, if there is an admissible cutoff u∈[0,1]u \in [0, 1] satisfying {x:λ(x)>u}⊆A\{x : \lambda(x) > u\} \subseteq A and ∑x∈Xmin⁡{λ(x),u}(1A(x)−(1−d))≥mu\sum_{x \in X} \min\{\lambda(x), u\}(\mathbf{1}_A(x) - (1-d)) \ge mu, then there is a largest admissible cutoff ε\varepsilon satisfying ∣{x:λ(x)>ε}∣≤m/d|\{x : \lambda(x) > \varepsilon\}| \le m/d.

For any finite nonempty set XX, 0<p<10 < p < 1, and A⊆2X\mathcal{A} \subseteq 2^X satisfying μp(A)>1/2\mu_p(\mathcal{A}) > 1/2, the family Bad2(A)={S⊆X:S⊈A1∪A2 for all A1,A2∈A}\mathrm{Bad}_2(\mathcal{A}) = \{S \subseteq X : S \not\subseteq A_1 \cup A_2 \text{ for all } A_1, A_2 \in \mathcal{A}\} is (p/(2C))(p/(2C))-small with C=25⋅5124C = 25 \cdot 512^4, without any monotonicity assumption on A\mathcal{A}.

Methods

Multiscale minimum-fragment method with maximal truncations: moving vertices to earlier colors to minimize total color-level movement subject to truncated mass inequalities, then grouping by final coloring and movement profile to bound failure probabilities.

Source excerpts

“For every a and H0 ∈ F, choose a feasible coloring z with U(a, z) ⊆ H0 minimizing L(a, z) = X x∈X (a(x) − z(x)), breaking ties by the fixed order.” · Show in paper

“Group the pairs (a, z) on the right of (2.6) by z and the array of counts nih = |{x : z(x) = i, a(x) = h}| (1 ≤ i < h ≤ s + 1).” · Show in paper

Selector-to-rounding conversion via exponential vertex weights: distributing fractional cover weights equally among vertices of each nonempty set and comparing lower and upper bounds on the expectation of Z=∑∅≠S⊆Xg(S)∏x∈SB4−a(x)Z = \sum_{\emptyset \ne S \subseteq X} g(S) \prod_{x \in S} B^{4 - a(x)}.

Source excerpts

“For each H ∈ F, define MH = X ∅̸=S⊆H g(S) ≥ 1 − g(∅) ≥ 1 2 , λH(x) = 1 MH X ∅̸=S⊆H x∈S g(S) |S| (x ∈ X).” · Show in paper

“Yx = B 4−a(x) , Z = X ∅̸=S⊆X g(S) Y x∈S Yx.” · Show in paper