OpenAI’s nested tournament sensitivity separator
Refutes $\mathrm{bs}=O(\mathrm{s}^2)$; a fixed seed yields an exponent strictly greater than two.
total arity: $N_0^m$ bits, with $N_0=LM^2(kr)^9$, $L=11$, $M=9^{10}$
Description
For depth $d$ and $M\ge9^{d+1}$, put $L=d+2$, $k=2M^2+1$ and $r=\lceil\sqrt M\rceil$. A regular tournament on $k$ rows is edge-labelled in $[r]$ with the forbidden-configuration property of Lemma 2.1. Begin with nested unions of Hamming balls of successive radii about $M$ disjoint weight-$L$ centres. Each recursive predicate is an OR over rows: its row’s strongest child predicates must all accept, while the edge-labelled children in outgoing rows must reject the chosen weaker predicate. Finally OR $M$ copies to balance 0- and 1-sensitivity. To obtain one asymptotic family, fix $d=9$, $M=9^{10}$ and an admissible labelling, and self-compose the resulting seed $m$ times.
Formal definition
Fix $d=9$, $M=9^{10}$, $L=11$, $k=2M^2+1$, $r=\lceil\sqrt M\rceil$, and a regular tournament with labels $a(i,j)\in[r]$ satisfying [OpenAISensitivity26, Lemma 2.1]. Choose $M$ disjoint weight-$L$ centres $z_h$ in $LM$ bits and set $P_{0,q}(x)=[\min_h\operatorname{dist}(x,z_h)\le10-q]$ for $1\le q\le10$. At level $\ell$, $1\le\ell\le9$, put $Q=11-\ell$, arrange $kr$ child inputs in rows, and define $$P_{\ell,q}(x)=\bigvee_{i\in[k]} \left(\bigwedge_{c\in[r]}P_{\ell-1,Q}(x_{i,c})\right) \left(\bigwedge_{i\to j}\neg P_{\ell-1,Q-q}(x_{j,a(i,j)})\right), \quad1\le q\le10-\ell.$$ Set $g=\mathrm{OR}_M\circ P_{9,1}$ and $F_m=g^{\circ m}$. All copies act on disjoint inputs. This is the fixed-seed family of Corollary 4.3.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{s}(f)\) Sensitivity | \(O(5843507755269244925453189084787151790243135958374678911440649158260034799828648025876463378968022^m)\) | Corollary 4.3: sensitivity ≤A^m, A=22M¹⁰. OpenAISensitivity26 |
| \(\mathrm{bs}(f)\) Block sensitivity | \(\Omega(36122005036315302778151792217492267728323576313688938488653910762565727724823376796778788409135057260835654187889331715677969332701578439948333928007781625724245588074795233962798724758384452483^m)\) | Corollary 4.3: block sensitivity at zero ≥B^m, B=M²(2M²+1)⁹. OpenAISensitivity26 |
Notes
Corollary 4.3 gives $\alpha=\log B/\log A>2$ and $\mathrm{bs}(F_m,0)\ge\mathrm{s}(F_m)^\alpha$. Theorem 1.1 separately gives $\mathrm{bs}/\mathrm{s}^2\ge2^d/[4(d+2)^2]$ for varying depth. The fixed exponent is small; the later Prove2Me’s refined tournament sensitivity family improves it substantially.