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

Quantitative lower bounds for trace reconstruction

Exact worst-case reconstruction of a binary word from independent deletion traces requires nΩ(log⁡log⁡n)n^{\Omega(\log \log n)} samples for every fixed deletion probability q∈(0,1)q \in (0, 1), even with unrestricted computation and any fixed positive success probability s∈(0,1]s \in (0, 1]. More generally, along every sequence of instances (n,q)(n, q) with n→∞n \to \infty, q∈(0,1)q \in (0, 1), and q3log⁡n→∞q^3 \log n \to \infty, for any fixed s∈(0,1]s \in (0, 1] and 0<c<1/(4log⁡2)0 < c < 1/(4 \log 2), Tq,s(n)≥nclog⁡(q3log⁡n)T_{q,s}(n) \ge n^{c \log(q^3 \log n)} eventually.

For every fixed deletion probability q∈(0,1)q \in (0, 1), lim⁡n→∞nAmin⁡x,y∈{0,1}n,x≠yTV(Dq(x),Dq(y))=0\lim_{n \to \infty} n^A \min_{x, y \in \{0, 1\}^n, x \neq y} \mathrm{TV}(\mathcal{D}_q(x), \mathcal{D}_q(y)) = 0 for every A>0A > 0, and at this same channel Tq,s(n)/nA→∞T_{q,s}(n)/n^A \to \infty for every fixed A>0A > 0 and s∈(0,1]s \in (0, 1].

Along every sequence with n→∞n \to \infty and δ3log⁡n→∞\delta^3 \log n \to \infty, for all sufficiently large instances there exist level-ii pairs satisfying Definition 2.2 simultaneously for 0≤i≤D0 \le i \le D, with C,ωC, \omega depending only on δ\delta and obeying log⁡C=O(Λ),log⁡(ω−1)=O(Λ)\log C = O(\Lambda), \log(\omega^{-1}) = O(\Lambda), and MBM_B depending only on BB.

For the parameters of Section 2, there is a choice of the common constants in Definition 2.2 with MB=1M_B = 1, ω=exp⁡(−C9Λ)\omega = \exp(-C_9 \Lambda) for an absolute constant C9C_9, and C>2C > 2 with log⁡C=O(Λ)\log C = O(\Lambda), for which a level-zero pair exists with simulation error E0≤ΔE_0 \le \Delta.

For 1≤i≤D1 \le i \le D, given a level-(i−1)(i-1) pair satisfying Definition 2.2 with constants C,ω,MBC, \omega, M_B, setting C′=max⁡{C,Cabs/ω}C' = \max\{C, C_{\mathrm{abs}}/\omega\} keeps all preceding levels valid and yields a level-ii pair with the same constants C′,ω,MBC', \omega, M_B, di=di−1+(bi−1)/4−.05d_i = d_{i-1} + (b_i - 1)/4 - .05, and Ei≤Δ+(ℓi/ℓi−1)Ei−1E_i \le \Delta + (\ell_i/\ell_{i-1})E_{i-1}.

For the parameters in Section 2, there are distinct words x,y∈{0,1}nx, y \in \{0, 1\}^n such that for every positive integer mm, TV(Dq(x)⊗m,Dq(y)⊗m)≤mn−dD+2mn(D+1)Δ\mathrm{TV}(\mathcal{D}_q(x)^{\otimes m}, \mathcal{D}_q(y)^{\otimes m}) \le \sqrt{m n^{-d_D}} + 2mn(D+1)\Delta, and in particular TV(Dq(x),Dq(y))≤n−dD/2+2n(D+1)Δ\mathrm{TV}(\mathcal{D}_q(x), \mathcal{D}_q(y)) \le n^{-d_D/2} + 2n(D+1)\Delta.

Methods

Channel reduction to a fixed working deletion rate δ=min⁡(q,1/2)\delta = \min(q, 1/2) by postprocessing δ\delta-traces with additional independent deletions of probability (q−δ)/(1−δ)(q - \delta)/(1 - \delta).

Source excerpts

“For the rest of the proof put δ = min(q, 1/2), Λ = δ−3δ^{−3}, HdelH_{del} = δ^3 log n. We use Tr(w) = D_δ(w) throughout the construction. The requested channel q is obtained by deleting each surviving bit of a δ-trace with additional probability (q − δ)/(1 − δ). Thus all upper bounds on distinguishability proved at δ also hold at q.” · Show in paper

Paired hiding mechanism using a joint common sublaw ω2(U⊗U)\omega^2(U \otimes U) of two side trace laws to conceal a fair orientation bit E∼Bernoulli(1/2)E \sim \mathrm{Bernoulli}(1/2) conditional on the flag and both reported side outputs.

Source excerpts

“Use one joint flag of probability ω^2 and output from U ⊗ U on it, otherwise reveal the bit and generate the two traces jointly from the normalized residual after subtracting ω^2 U ⊗ U from the product law for that orientation. Marginalizing flags yields the requisite conditionally independent pair traces given orientations. Conditional on the augmented pair data, the bit remains fair on the hidden event.” · Show in paper

Conditioning preliminary oracle laws on a common event of typical metadata and lower-bounded reference density Gx≥1/2G_x \ge 1/2 to obtain likelihood domination ν≪μ\nu \ll \mu and controlled Lri(μ)L^{r_i}(\mu) score moments.

Source excerpts

“Condition each preliminary law separately on the same joint event AkeepA_{keep} consisting of typical metadata and G_x ≥ 1/2. Its complement has joint reference measure on the typical part ≤ (2 N_i−ρi^{−ρ})^{r_i}, hence bad mass o(∆) under each preliminary law by Cauchy–Schwarz, the moment bound, and the common atypical mass.” · Show in paper

Prouhet–Thue–Morse signed motif cancellation convolved with hidden binomial offsets to suppress low-order singleton terms in likelihood score expansions.

Source excerpts

“Lemma 5.2 (Signed binomial smoothing). Let σ be the Prouhet–Thue–Morse sequence of order s_* above. Suppose π is an integer translation or reflection of a fair binomial probability mass function with g ≥ c_0 ω^2 m trials, where c_0 > 0 is absolute and m → ∞ as in the construction.” · Show in paper

Recursive tree of randomly displaced windows with local and global paired chunks to hide motif locations at multiple nested depths.

Source excerpts

“Reserve t_j local pairs in each part. For 1 ≤ v ≤ t_j, a fair bit Eu,vE_{u,v}^{loc} gives a pre chunk of hj−1h_{j−1} + Eu,vE_{u,v}^{loc} pure Uj−1U_{j−1}^+ atoms and a post chunk of hj−1h_{j−1} + 1 − Eu,vE_{u,v}^{loc} such atoms. Also reserve global pairs between distant parts.” · Show in paper

Multi-gadget concatenation and posterior factorization to amplify a 2/32/3 two-point testing lower bound to arbitrary fixed positive success probability s∈(0,1]s \in (0, 1].

Source excerpts

“Take g independent fair choices between the two length-N words, concatenate the chosen words, and append a common known tail of length n − gN. This gives 2^g distinct length-n hypotheses. Give the estimator the stronger observation in which every trace is separated at the gadget boundaries, together with an independent trace of the tail.” · Show in paper