OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction · §1

The machine model: Programs on bit stacks with coin flips and independence queries, counting oracle calls and bit operations, and a polynomial resource bound

A randomized oracle machine on stacks of bits.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Let M1M_1 and M2M_2 be matroids on the ground set {0,1,…,n−1}\{0,1,\dots,n-1\}, known only through independence oracles, and let ZZ be the number of their common bases. A fully polynomial randomized approximation scheme (FPRAS) for ZZ is a randomized algorithm that takes an accuracy ε\varepsilon and a failure probability δ\delta and runs in time polynomial in nn, 1/ε1/\varepsilon and log⁡(1/δ)\log(1/\delta). Bounding the running time and the oracle calls of such an algorithm needs a machine; the one here is a register machine whose registers are stacks of bits and whose random choices are read from a tape.

Oracles and Bit Strings

An independence oracle on nn elements is a map O:{0,1}×{0,1}n→{0,1}O\colon \{0,1\}\times\{0,1\}^n\to\{0,1\}.✦ The oracle of M1M_1 and M2M_2 has O(0,x)=1O(0,x)=1 exactly when the set with indicator vector xx is independent in M1M_1, and O(1,x)=1O(1,x)=1 exactly when it is independent in M2M_2.

A bit string u=u0u1⋯u=u_0u_1\cdots has length |u||u|, and λ\lambda is the empty string. The binary value of a bit string uu is the natural number val⁡(u)=∑j<|u|uj2j,\operatorname{val}(u)=\sum_{j<|u|}u_j\,2^j,(1)✦ and for a natural number mm, ⟨m⟩\langle m\rangle is the string of binary digits of mm, lowest digit first, with ⟨0⟩=λ\langle 0\rangle=\lambda.

The Definition

Definition 1. Fix natural numbers kk and ss; the registers are 0,1,…,k+70,1,\dots,k+7 and the states are 0,1,…,s0,1,\dots,s. An instruction is one of 𝗉𝗎𝗌𝗁(i,b,q′),𝗉𝗈𝗉(i,q⌀,q0,q1),𝖼𝗈𝗂𝗇(q0,q1),𝗊𝗎𝖾𝗋𝗒(w,i,q0,q1),𝗁𝖺𝗅𝗍,\mathsf{push}(i,b,q'),\quad \mathsf{pop}(i,q_\varnothing,q_0,q_1),\quad \mathsf{coin}(q_0,q_1),\quad \mathsf{query}(w,i,q_0,q_1),\quad \mathsf{halt},(2)✦ where ii is a register, bb and ww are bits, and q′,q⌀,q0,q1q',q_\varnothing,q_0,q_1 are states; ℐk,s\mathcal{I}_{k,s} is the set of instructions. A program is a map P:{0,1,…,s}→ℐk,sP\colon \{0,1,\dots,s\}\to\mathcal{I}_{k,s}(3)✦ that assigns an instruction to each state. A configuration is a tuple c=(R0,…,Rk+7;q;y;N;T)c=(R_0,\dots,R_{k+7};\,q;\,y;\,N;\,T)(4)✦ of the register contents RiR_i, bit strings read as stacks whose first bit is the top, a state qq, an output yy that is a rational number or undefined (y=⊥y=\bot), the number NN of oracle calls and the number TT of bit operations.

The machine takes as input natural numbers nn and rr, where rr is a second natural-number parameter of the input, and rationals ε=a/b\varepsilon=a/b and δ=a′/b′\delta=a'/b' in lowest terms with b,b′>0b,b'>0; the input length is ℓ(n,r,ε,δ)=6+|⟨n⟩|+|⟨r⟩|+|⟨|a|⟩|+|⟨b⟩|+|⟨|a′|⟩|+|⟨b′⟩|,\ell(n,r,\varepsilon,\delta)=6+|\langle n\rangle|+|\langle r\rangle|+|\langle |a|\rangle| +|\langle b\rangle|+|\langle |a'|\rangle|+|\langle b'\rangle|,(5)✦ and the initial configuration is cin(n,r,ε,δ)=(⟨n⟩,⟨r⟩,⟨|a|⟩,⟨b⟩,⟨|a′|⟩,⟨b′⟩,λ,…,λ;0;⊥;0;0).c_{\mathrm{in}}(n,r,\varepsilon,\delta)=\bigl(\langle n\rangle,\langle r\rangle, \langle |a|\rangle,\langle b\rangle,\langle |a'|\rangle,\langle b'\rangle, \lambda,\dots,\lambda;\,0;\,\bot;\,0;\,0\bigr).(6)✦

For a program PP, an independence oracle OO on nn elements and a bit ρ\rho, the transition map sends a configuration c=(R0,…,Rk+7;q;y;N;T)c=(R_0,\dots,R_{k+7};\,q;\,y;\,N;\,T) to cc itself when y≠⊥y\neq\bot, and when y=⊥y=\bot to step⁡P,O(ρ,c)={c[Ri:=bRi,q:=q′,T:=T+1]P(q)=𝗉𝗎𝗌𝗁(i,b,q′),c[q:=q⌀,T:=T+1]P(q)=𝗉𝗈𝗉(i,q⌀,q0,q1),Ri=λ,c[Ri:=u,q:=qa,T:=T+1]P(q)=𝗉𝗈𝗉(i,q⌀,q0,q1),Ri=au,c[q:=qρ,T:=T+1]P(q)=𝖼𝗈𝗂𝗇(q0,q1),c[q:=qO(w,Ri),N:=N+1,T:=T+|Ri|+n+1]P(q)=𝗊𝗎𝖾𝗋𝗒(w,i,q0,q1),|Ri|=n,c[y:=0,T:=T+|Ri|+n+1]P(q)=𝗊𝗎𝖾𝗋𝗒(w,i,q0,q1),|Ri|≠n,c[y:=val⁡(R6)/val⁡(R7),T:=T+|R6|+|R7|+1]P(q)=𝗁𝖺𝗅𝗍.\operatorname{step}_{P,O}(\rho,c)= \begin{cases} c[R_i:=bR_i,\ q:=q',\ T:=T+1] & P(q)=\mathsf{push}(i,b,q'),\\ c[q:=q_\varnothing,\ T:=T+1] & P(q)=\mathsf{pop}(i,q_\varnothing,q_0,q_1),\ R_i=\lambda,\\ c[R_i:=u,\ q:=q_a,\ T:=T+1] & P(q)=\mathsf{pop}(i,q_\varnothing,q_0,q_1),\ R_i=au,\\ c[q:=q_\rho,\ T:=T+1] & P(q)=\mathsf{coin}(q_0,q_1),\\ c[q:=q_{O(w,R_i)},\ N:=N+1,\ T:=T+|R_i|+n+1] & P(q)=\mathsf{query}(w,i,q_0,q_1),\ |R_i|=n,\\ c[y:=0,\ T:=T+|R_i|+n+1] & P(q)=\mathsf{query}(w,i,q_0,q_1),\ |R_i|\neq n,\\ c[y:=\operatorname{val}(R_6)/\operatorname{val}(R_7),\ T:=T+|R_6|+|R_7|+1] & P(q)=\mathsf{halt}. \end{cases}(7)✦ Here c[⋯]c[\cdots] is cc with the listed entries replaced, and aa is the top bit of Ri=auR_i=au. A query reads its register Ri=u0⋯un−1R_i=u_0\cdots u_{n-1} as the vector (u0,…,un−1)(u_0,\dots,u_{n-1}), and a halt with val⁡(R7)=0\operatorname{val}(R_7)=0 outputs 00.

The run of PP with oracle OO from a configuration cc on a tape β=β0β1β2⋯\beta=\beta_0\beta_1\beta_2\cdots of bits is the sequence of configurations c(0)=c,c(t+1)=step⁡P,O(βt,c(t))(t≥0).c^{(0)}=c,\qquad c^{(t+1)}=\operatorname{step}_{P,O}\bigl(\beta_t,c^{(t)}\bigr)\quad(t\ge 0).(8)✦ A bit string β=β0⋯βB−1\beta=\beta_0\cdots\beta_{B-1} of length BB is read as the infinite tape β‾\bar\beta that agrees with β\beta on its first BB bits and is 00 afterwards: β‾t=βt(t<B),β‾t=0(t≥B).\bar\beta_t=\beta_t\ \ (t<B),\qquad \bar\beta_t=0\ \ (t\ge B).(9)✦

For natural numbers CC and dd, the resource bound bound⁡C,d\operatorname{bound}_{C,d} is the function of n,r,ε,δn,r,\varepsilon,\delta given by bound⁡C,d(n,r,ε,δ)=C(1+n+ℓ(n,r,ε,δ)+⌈1/ε⌉+⌈log⁡2⌈1/δ⌉⌉)d,\operatorname{bound}_{C,d}(n,r,\varepsilon,\delta)=C\,\bigl(1+n+\ell(n,r,\varepsilon,\delta) +\lceil 1/\varepsilon\rceil+\lceil\log_2\lceil 1/\delta\rceil\rceil\bigr)^d,(10)✦ where ⌈x⌉\lceil x\rceil is the least natural number at least xx and ⌈log⁡2m⌉\lceil\log_2 m\rceil is the least natural number jj with m≤2jm\le 2^j.

In the paper, the model reads: a randomized oracle algorithm, whose oracle calls are counted apart from its other bit operations.

What Is Checked

The machine model is stated over the independence oracle on nn elements, which the query instruction consults, and over the binary value val\operatorname{val}, through which the halt instruction reads registers 66 and 77 as its output.