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

Variance of the Random k-SAT Hitting Time

For every fixed integer k≥3k \ge 3, let HnH_n be the first unsatisfiable prefix index in random kk-SAT on nn variables with independent uniform proper kk-clauses, and let Tn,B=min⁡{Hn,⌊Bn⌋}T_{n,B} = \min\{H_n, \lfloor Bn \rfloor\}. With ℓk(n)=log⁡(en)\ell_k(n) = \log(en) for k=3k=3 and 11 for k≥4k \ge 4, and Uk=log⁡2−log⁡(1−2−k)U_k = \frac{\log 2}{-\log(1 - 2^{-k})}, there exist constants Ck,ck>0C_k, c_k > 0 such that Var(Hn)≤Cknℓk(n)\mathrm{Var}(H_n) \le C_k n \ell_k(n) for all n≥kn \ge k and Var(Hn)≥ckn\mathrm{Var}(H_n) \ge c_k n for all sufficiently large nn. For every fixed B>0B > 0 there is Ck,B<∞C_{k,B} < \infty such that Var(Tn,B)≤Ck,Bnℓk(n)\mathrm{Var}(T_{n,B}) \le C_{k,B} n \ell_k(n) for all n≥kn \ge k, and if B>UkB > U_k, then Var(Tn,B)≥ckn\mathrm{Var}(T_{n,B}) \ge c_k n for all sufficiently large nn (with the size cutoff allowed to depend on kk and BB).

For an integer k≥3k \ge 3, β=k/(k−1)\beta = k/(k-1), Kk=(2k(k−1))k−1K_k = (2^k(k-1))^{k-1}, and Ck=4(2Kk)1/(k−1)C_k = 4(2K_k)^{1/(k-1)}, every integer u≥ku \ge k, every S⊆{0,1}uS \subseteq \{0,1\}^u, and every integer d≥1d \ge 1 satisfy τk(S)qd(S)β≤Ckdβ\tau_k(S) q_d(S)^\beta \le C_k d^\beta, with no upper restriction on dd and no positive lower cutoff on qd(S)q_d(S).

For each fixed integer k≥3k \ge 3, the killing-probability exponent β=k/(k−1)\beta = k/(k-1) in Proposition 2.3 and the block-error exponent k−1k-1 in Lemma 2.1 are optimal for bounds uniform over arbitrary assignment sets S⊆{0,1}uS \subseteq \{0,1\}^u.

For k=3k=3 and c∈[0,8]c \in [0, 8], let sn(c)s_n(c) be the satisfiability probability for Pois(cn)\mathrm{Pois}(cn) clauses with replacement of variables within clauses, and let ωn=E[min⁡{Hn−1,10n}]/n\omega_n = \mathbb{E}[\min\{H_n - 1, 10n\}]/n. Uniformly for c∈[0,8]c \in [0, 8], c≤ωn−2n−1/12  ⟹  sn(c)≥e−24/2c \le \omega_n - 2n^{-1/12} \implies s_n(c) \ge e^{-24}/2, and c≥ωn+2n−1/12  ⟹  sn(c)=O(n−1/6)c \ge \omega_n + 2n^{-1/12} \implies s_n(c) = O(n^{-1/6}).

Fix k≥3k \ge 3, B>0B > 0, and 0<δ<1/20 < \delta < 1/2. If en=E[min⁡{Hn,⌊Bn⌋}]/ne_n = \mathbb{E}[\min\{H_n, \lfloor Bn \rfloor\}]/n satisfies a≤en≤A<Ba \le e_n \le A < B and P(∣Tn−μn∣≥n1−δ)≤ηn→0\mathbb{P}(|T_n - \mu_n| \ge n^{1-\delta}) \le \eta_n \to 0 for all sufficiently large nn, then there is a finite constant K≥0K \ge 0 such that en1+n2≥min⁡{en1,en2}−Kn−δe_{n_1+n_2} \ge \min\{e_{n_1}, e_{n_2}\} - K n^{-\delta} (for n=min⁡{n1,n2}n = \min\{n_1, n_2\} sufficiently large, with no restriction on n1/n2n_1/n_2) and en+1≥en−Kn−δe_{n+1} \ge e_n - K n^{-\delta}. Moreover ene_n converges to a number α∈[a,A]\alpha \in [a, A] and Pn(⌊cn⌋)→1P_n(\lfloor cn \rfloor) \to 1 for 0≤c<α0 \le c < \alpha and 00 for c>αc > \alpha.

For independent uniform proper 33-clauses on n≥3n \ge 3 variables and Tn=min⁡{Hn,10n}T_n = \min\{H_n, 10n\}, there is an absolute constant CC such that Var(Tn)≤Cn(log⁡n)4\mathrm{Var}(T_n) \le C n (\log n)^4 for all integers n≥3n \ge 3.

Methods

Coordinate-omission form of the Efron-Stein inequality via martingale differences

Source excerpts

“Lemma 3.1 (Coordinate omission). For the independent clause process above, Var(T) ≤ sum_{i=1}^L E D_i^2.” · Show in paper

Two-filtration conditioning exposing root types and nonordinary clauses through the cap while keeping ordinary clauses and nonroot parts of test clauses independent

Source excerpts

“Lemma 3.2 (Conditional product law). Conditional on E, the clauses at indices in O are independent uniform proper k-clauses on the u nonroots. The nonroot parts at indices in Q are independent uniform proper (k − 1)-clauses on the nonroots. These two collections are mutually independent.” · Show in paper

Sequential one-clause replacement of shorter (k-1)-clauses by blocks of proper k-clauses

Source excerpts

“Lemma 2.2 (Sequential replacement). For integers k ≥ 3 and u ≥ k, every S ⊆ {0, 1}^u, and all integers d, g ≥ 1, RdgR_{dg}(S) ≥ q_d(S) − d K_k g−(k−1)g^{-(k−1)}.” · Show in paper

Layer-cake integration of conditional occupation time above a killing-probability level

Source excerpts

“Since 0 ≤ qm ≤ 1, the layer-cake identity and Lemma 4.1 give sum_{m=i}^{L-1} E[1_{S_m != empty} q_m^gamma | E] = int_0^1 gamma agamma−1a^{gamma-1} sum_{m=i}^{L-1} P(S_m != empty, q_m >= a | E) da” · Show in paper

Joint moment bounds for root incidences and collisions using falling factorials

Source excerpts

“For every nonnegative function f on the nonnegative integers and 1 ≤ r ≤ M, E[f(Z)(V)_r] = (M)_r p_2^r E f(r + X), X ~ Bin(M − r, p1).” · Show in paper

Conversion of quantile separation to a linear variance lower bound allowing atoms

Source excerpts

“For an independent copy X', each of the disjoint events {X ≤ a, X' ≥ b} and {X' ≤ a, X ≥ b} has probability at least 1/16 once b > a. Therefore Var(X) = (1/2) E(X - X')^2 >= (b - a)^2 / 16 >= (d_k^2 / 64) n” · Show in paper

Proper-clause one-clause interpolation between local-block formulas and diluted global formulas

Source excerpts

“Lemma B.2 (Proper-clause trial comparison). ... Q_dil >= Q_loc - C_k M epsilon^{-k} sum_{j=1}^2 w_j / n_j^k” · Show in paper