Introduction
A selector is an algorithm that chooses one of two strings and chooses a member of a language L L L whenever either string belongs to L L L . Suppose the algorithm runs in polynomial time. How much advice, common to all n n n -bit inputs, suffices to decide membership in L L L ? Ko’s argument gives a short proof of a quadratic upper bound [14 ] . View the n n n -bit strings as the vertices of a tournament, and direct each edge from the chosen string to the other one. Every member beats every nonmember. Among any remaining members, some vertex is beaten by at least half of them when equality counts. Store that vertex and repeat on the members it fails to certify. The resulting list of at most n + 1 n+1 n + 1 names recognizes L L L at length n n n . Its cost comes from writing down n n n bits per name.
Prior work. Selman introduced P-selective sets as the polynomial-time analogue of the semirecursive sets [22 ] . Ko’s quadratic bound has remained the deterministic upper bound. Nondeterministic interpreters do much better: Hemaspaandra and Torenvliet showed that n + 1 n+1 n + 1 advice bits suffice for NP interpreters and that n n n bits do not [12 ] . A linear deterministic bound therefore follows from P = NP, and Hemaspaandra, Hempel and Nickelsen derived it from the assumption that every P-selective language has an associative selector [11 ] . Domination numbers of tournaments save only a lower-order term: the bound of Szekeres and Szekeres [21 , 18 ] gives n 2 − n log 2 n + O ( n ) n^2-n\log_2 n+O(n) n 2 − n log 2 n + O ( n ) bits. In the comparison model, our earlier work [5 Theorems 5.5 and 5.6] gave a lower bound with leading coefficient 1 / 4 1/4 1/4 for polynomially many adaptive Boolean queries and an unrestricted-time upper bound with coefficient 1 / 2 1/2 1/2 .
We close this interval, extend the lower bound to algebraic queries of individual degree two, and bring the upper bound to polynomial time under a standard derandomization hypothesis. The hypothesis cannot be used to go further by any relativizing argument.
The model. Put N = 2 n N=2^n N = 2 n . A legal cut consists of a tournament E E E on { 0 , 1 } n \{0,1\}^n { 0 , 1 } n and a marked set P P P all of whose vertices beat every vertex outside P P P . Write x ≻ y x\succ y x ≻ y for E ( x , y ) = 1 E(x,y)=1 E ( x , y ) = 1 and set E ( x , x ) = 0 E(x,x)=0 E ( x , x ) = 0 . An asymmetric selector induces this table by sorting its two arguments before evaluating it. A decoder receives an input vertex, advice, and access to the table. Its program is independent of the marked tournament. An algebraic query specifies a finite field with its canonical encoding and a point of F 2 n \mathbb{F}^{2^n} F 2 n . The answer is the value of one fixed polynomial per field agreeing with E E E on the Boolean cube. Degree bounds are per variable. All queries are classical. Between queries we allow unrestricted computation except in results explicitly specifying polynomial time.
Theorem 1.1 (The ordinary advice threshold). Every legal cut has a zero-error decoder using n 2 / 4 + O ( n ) n^2/4+O(n) n 2 /4 + O ( n ) ordinary advice bits and at most n n n nonadaptive Boolean comparisons. One computable decoder works for all lengths and cuts. Conversely, for each fixed randomized interpreter making polynomially many adaptive queries and every sufficiently large n n n , some cut and some fixed degree-two extensions require n 2 / 4 − O q ( n log n ) n^2/4-O_q(n\log n) n 2 /4 − O q ( n log n ) ordinary advice bits for pointwise error 1 / 3 1/3 1/3 .
Here O q ( ⋅ ) O_q(\cdot) O q ( ⋅ ) allows the constant to depend on the polynomial query bound. The advice in the lower bound may depend on the entire realized oracle, including its extensions, and the decoder’s computation between queries is unrestricted. The lower bound is therefore information-theoretic, and the upper bound matches it with Boolean comparisons alone.
Theorem 1.2 (Degree one). With direct access to the canonical multilinear extensions, deterministic polynomial time and n + 1 n+1 n + 1 fixed-width advice bits suffice for exact recognition. This width is optimal even with the entire table available.
The decoder reads deg + ( x ) \deg^+(x) deg + ( x ) from row evaluations: x ∈ P x\in P x ∈ P precisely when deg + ( x ) ≥ N − ∣ P ∣ \deg^+(x)\ge N-|P| deg + ( x ) ≥ N − ∣ P ∣ . One public odd prime greater than N N N suffices for a single query; a uniform algorithm uses O ( n / log ( n + 1 ) ) O(n/\log(n+1)) O ( n / log ( n + 1 )) small-prime queries. Thus multilinear access gives a deterministic decoder exactly the advice that NP interpreters need [12 ] , while access of individual degree two already costs the full quarter. In the language of Aaronson and Wigderson [AW08], the advice complexity of selectors is a natural quantity on which algebraic query access of degree one and of degree two separate quadratically. Theorems 1.1 and 1.2 are proved in § 2 , § 6 and § 7 .
Oblivious equilibrium search. Suppose two players have N N N actions each. Before seeing the payoffs, we choose a distribution on pairs of mixed strategies. What is the greatest probability with which one draw is an approximate Nash equilibrium, even for the worst game? The question measures the information needed to name a successful strategy. With access to the full payoff matrix an explicit zero-sum game can be solved by linear programming.
Daskalakis and Papadimitriou [DP09] called such procedures oblivious: the algorithm samples a fixed distribution on pairs of mixed strategies, and the game is used only to check whether the sample is an approximate equilibrium. Sampling arguments of Althöfer [2 ] and Lipton and Young [16 ] for zero-sum games, and of Lipton, Markakis and Mehta [17 ] for bimatrix games, give empirical strategies of length O ( log N / ϵ 2 ) O(\log N/\epsilon^2) O ( log N / ϵ 2 ) . A uniform draw from the resulting list of profiles succeeds with probability at least 2 − O ( n 2 / ϵ 2 ) 2^{-O(n^2/\epsilon^2)} 2 − O ( n 2 / ϵ 2 ) , where n = log 2 N n=\log_2 N n = log 2 N . Babichenko, Barman and Peretz [4 ] studied simple approximate equilibria in games with many players.
Daskalakis and Papadimitriou [DP09, extended version, proof of Theorem 4, Claim 3] show that finding a δ \delta δ -well-supported equilibrium can require Ω ( 2 ( 0.8 − 34 δ ) n 2 ) \Omega(2^{(0.8-34\delta)n^2}) Ω ( 2 ( 0.8 − 34 δ ) n 2 ) oblivious proposals in expectation for bimatrix games with payoffs in [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] . Setting the negative payoffs in their construction to zero gives the same coefficient 0.8 − 34 ϵ 0.8-34\epsilon 0.8 − 34 ϵ for ordinary additive regret on our [ 0 , 1 ] [0,1] [ 0 , 1 ] scale (Remark A.7). Kothari and Mehta [13 ] proved a 2 Ω ( n 2 ) 2^{\Omega(n^2)} 2 Ω ( n 2 ) lower bound for ordinary regret at a sufficiently small fixed error, even with access to a sum-of-squares relaxation and a partial verification oracle. For symmetric constant-sum games we determine the sharp coefficient for every fixed 0 < ϵ < 1 / 2 0<\epsilon<1/2 0 < ϵ < 1/2 . It grows as ( ln 2 ) / ( 8 ϵ 2 ) (\ln2)/(8\epsilon^2) ( ln 2 ) / ( 8 ϵ 2 ) as ϵ → 0 \epsilon\to0 ϵ → 0 .
Theorem 1.3 (Equilibrium search). Let P ϵ ( N ) P_\epsilon(N) P ϵ ( N ) be the optimal worst-case success probability of one oblivious proposal for symmetric constant-sum games, normalized so A i j + A j i = 1 A_{ij}+A_{ji}=1 A ij + A j i = 1 and A i j ∈ [ 0 , 1 ] A_{ij}\in[0,1] A ij ∈ [ 0 , 1 ] . Put n = log 2 N n=\log_2N n = log 2 N and c ϵ = 1 − H 2 ( 1 / 2 + ϵ ) c_\epsilon=1-H_2(1/2+\epsilon) c ϵ = 1 − H 2 ( 1/2 + ϵ ) . For fixed 0 < ϵ < 1 / 2 0<\epsilon<1/2 0 < ϵ < 1/2 ,
− log 2 P ϵ ( N ) = n 2 4 c ϵ + O ϵ ( n log n ) . -\log_2 P_\epsilon(N)=\frac{n^2}{4c_\epsilon}+O_\epsilon(n\log n). − log 2 P ϵ ( N ) = 4 c ϵ n 2 + O ϵ ( n log n ) . The same leading exponent holds for proposals with N o ( 1 ) N^{o(1)} N o ( 1 ) adaptive payoff queries, and for the logarithm of the smallest list that works for every game. If ϵ → 0 \epsilon\to0 ϵ → 0 and log ( 1 / ϵ ) = o ( n ) \log(1/\epsilon)=o(n) log ( 1/ ϵ ) = o ( n ) , the sharp exponent for oblivious proposals in the class of all symmetric bimatrix games is ( ln 2 / 8 + o ( 1 ) ) n 2 / ϵ 2 (\ln2/8+o(1))n^2/\epsilon^2 ( ln 2/8 + o ( 1 )) n 2 / ϵ 2 .
The factor four has a direct comparison. A column strategy is ϵ \epsilon ϵ -secure in a value-1 / 2 1/2 1/2 game if every pure row earns at most 1 / 2 + ϵ 1/2+\epsilon 1/2 + ϵ against it. For this same task, with the value known, the logarithmic cost of oblivious search has leading term n 2 / ( 4 c ϵ ) n^2/(4c_\epsilon) n 2 / ( 4 c ϵ ) in symmetric constant-sum games and n 2 / c ϵ n^2/c_\epsilon n 2 / c ϵ in arbitrary zero-sum payoff matrices (Theorem A.3). The second exponent is what sampling an optimal strategy achieves, as in the arguments of Althöfer and of Lipton and Young, so their sampling is exactly optimal for oblivious search in zero-sum games. Symmetry saves a factor four, the same factor that separates Ko’s bound from Theorem 1.1 .
The proof chooses a distribution on actions and a sample length r r r together. With this distribution, at least half the samples give a secure strategy, and at least 2 ϵ r 2 − O ( r ) 2^{\epsilon r^2-O(r)} 2 ϵ r 2 − O ( r ) different ordered samples succeed. This offsets c ϵ r 2 c_\epsilon r^2 c ϵ r 2 of the n r nr n r bits needed to specify one sample. The worst length is near n / ( 2 c ϵ ) n/(2c_\epsilon) n / ( 2 c ϵ ) . Conversely, a tournament with a hidden set of about N \sqrt{N} N winning actions makes this cost necessary even for proposals using arbitrary real probabilities. § 3 gives the sampler, and Appendix § 10 proves the lower bound and the extensions.
Bounded error and the cost of confidence. An ordinary advice word is fixed before the random tape is drawn, so repeating a bounded-error decoder on fresh coins reuses the same word. This is why the lower bound in Theorem 1.1 already holds at error 1 / 3 1/3 1/3 . Advice that may depend on the realized public tape behaves differently: at constant error it permits linear advice [3 ] . How the cost of such advice, and of coherent quantum advice, grows as the error decreases is the subject of a separate paper. Nothing here depends on it.
Polynomial time. Let H denote the hypothesis that for some c > 0 c > 0 c > 0 a Boolean function in E = DTIME ( 2 O ( n ) ) E = \operatorname{DTIME}(2^{O(n)}) E = DTIME ( 2 O ( n ) ) requires circuits of size 2 c n 2^{cn} 2 c n with SAT gates on all sufficiently large input lengths. Our efficient decoder uses the logarithmic-seed generator for SAT-gate tests supplied by this hypothesis [15 , 23 ] .
Theorem 1.4 (Efficient recognition under H). Under H, every P-selective language L L L has a deterministic polynomial-time decoder using n 2 / 4 + O L ( n ) n^2/4 + O_L(n) n 2 /4 + O L ( n ) ordinary advice bits. If the smaller nonempty side at length n n n has K K K vertices, the decoder makes at most ⌈ log 2 K ⌉ + 1 ≤ n \lceil\log_2 K\rceil+ 1 \le n ⌈ log 2 K ⌉ + 1 ≤ n nonadaptive selector comparisons.
The computable and polynomial-time decoders thus attain the same additive order above n 2 / 4 n^2/4 n 2 /4 . The constant hidden in O L ( n ) O_L(n) O L ( n ) may depend on the fixed selector. Earlier conditional improvements of Ko’s bound assume P = NP or associative selectors. Theorem 1.4 needs only a circuit lower bound of the kind used to derandomize Arthur–Merlin protocols. The next theorem shows that this is the end of the line for arguments that treat the selector as an oracle.
Theorem 1.5 (Relativized sharpness). There are an oracle O O O and a degree-two extension family O ~ \widetilde{O} O of it such that H O H^O H O holds, every P O P^O P O -selective language L ′ L' L ′ has a polynomial-time decoder relative to O O O with n 2 / 4 + O L ′ ( n ) n^2/4 + O_{L'}(n) n 2 /4 + O L ′ ( n ) advice bits, and some P O P^O P O -selective language is not in BPP O ~ / ⌊ c n 2 ⌋ \operatorname{BPP}^{\widetilde{O}}/\lfloor cn^2\rfloor BPP O / ⌊ c n 2 ⌋ for any c < 1 / 4 c < 1/4 c < 1/4 .
Consequently no relativizing proof can derive advice ( 1 / 4 − δ ) n 2 (1/4-\delta)n^2 ( 1/4 − δ ) n 2 for P-selective languages from H, and neither can a proof that algebrizes in the sense of Aaronson and Wigderson [AW08] with extensions of individual degree two. Section 9 gives the construction; it is Theorem 9.1.
Where the quarter comes from
The strong components of a tournament are totally ordered, and a legal cut falls between two consecutive ones. Only the smaller of these two components matters.
Theorem 1.6 (Boundary components). For a nontrivial legal cut let B B B be the size of the smaller of the two strong components adjacent to it, v = log 2 B v = \log_2 B v = log 2 B and u = min { v , n / 2 } u = \min\{v,n/2\} u = min { v , n /2 } . A computable decoder uses u ( n − u ) + O ( n ) u(n-u) + O(n) u ( n − u ) + O ( n ) advice bits. For every polynomial-query randomized decoder with degree-two access, every large n n n and every 3 ≤ B ≤ 2 n − 1 3 \le B \le2^{n-1} 3 ≤ B ≤ 2 n − 1 , some cut with this boundary size requires u ( n − u ) − O q ( n log n ) u(n-u)-O_q(n\log n) u ( n − u ) − O q ( n log n ) bits at error 1 / 3 1/3 1/3 . For a P-selective language, a deterministic polynomial-time decoder needs n ( ⌊ v ⌋ + 1 ) + O ( 1 ) n(\lfloor v\rfloor+ 1) + O(1) n (⌊ v ⌋ + 1 ) + O ( 1 ) bits unconditionally and u ( n − u ) + O L ( n ) u(n-u) + O_L(n) u ( n − u ) + O L ( n ) bits under H.
When log n ≪ v = o ( n ) \log n \ll v = o(n) log n ≪ v = o ( n ) the cost is therefore ( 1 + o ( 1 ) ) n v (1+o(1))nv ( 1 + o ( 1 )) n v , and it is attained in polynomial time with no hypothesis. The quarter coefficient already appears at B = 2 ⌈ n / 2 ⌉ B = 2^{\lceil n/2\rceil} B = 2 ⌈ n /2 ⌉ , and larger boundary components do not raise it. The same exponent governs tournaments without any reference to advice (Section 4). In the worst case a random t t t -subset of an N N N -vertex tournament dominates with probability 2 − ( 1 / 4 + o ( 1 ) ) log 2 ( N / t ) 2^{-(1/4+o(1))\log^2(N/t)} 2 − ( 1/4 + o ( 1 )) l o g 2 ( N / t ) , and every tournament on { 0 , 1 } n \{0,1\}^n { 0 , 1 } n has a dominating set of Kolmogorov complexity n 2 / 4 + O ( n ) n^2/4 + O(n) n 2 /4 + O ( n ) , which is tight. The lower bound embeds the hard instances of Theorem 1.1 under a public block of padding vertices joined to them by two private edges (Section 8).
Orient the smaller side S S S so that it beats its complement. A list of vertices of S S S covers S S S if every x ∈ S x \in S x ∈ S equals or beats an entry. A uniform ambient r r r -tuple has n r nr n r bits in its description. If at least 2 r 2 − O ( r ) 2^{r^2-O(r)} 2 r 2 − O ( r ) different tuples cover S S S , its chance of being a cover is at least 2 − r ( n − r ) − O ( r ) 2^{-r(n-r)-O(r)} 2 − r ( n − r ) − O ( r ) . A common list of candidate tuples can then serve all tournaments, and it costs only r ( n − r ) + O ( n ) r(n-r)+O(n) r ( n − r ) + O ( n ) bits to name a cover in that list. The maximum of r ( n − r ) r(n-r) r ( n − r ) is n 2 / 4 n^2/4 n 2 /4 . The central point is to find a length r r r at which both coverage and multiplicity hold.
For example, if a vertex loses to every other vertex of S S S , every cover must contain it. Sampling uniformly from S S S can take order ∣ S ∣ |S| ∣ S ∣ draws just to hit this one vertex. We give a vertex more weight when the current distribution of anchors is likely to miss it. If s ν ( x ) s_\nu(x) s ν ( x ) is the miss probability, the fixed point has weights p ( x ) ∝ s ν ( x ) J p(x) \propto s_\nu(x)^J p ( x ) ∝ s ν ( x ) J and uses a slight smoothing ν \nu ν of p p p . The normalization chooses J J J so that r = ⌈ J ⌉ r=\lceil J\rceil r = ⌈ J ⌉ independent samples cover with constant probability. The tournament identity also controls ∑ x ν ( x ) 1 + 1 / J \sum_x \nu(x)^{1+1/J} ∑ x ν ( x ) 1 + 1/ J . Hölder’s inequality then turns probability mass on covers into the required count. Section 2 gives the proof.
The same count applies to any subtournament whose covers recognize the cut, in particular to a boundary component, which gives the upper bound in Theorem 1.6 .
To recover a cover in polynomial time, testing whether an entire tuple covers S S S would require certifying a statement about every vertex. Instead the decoder’s existence proof certifies how much of the remaining weight a short block of anchors covers. This is a lower bound on the size of a nondeterministically recognized set. One potential pays for uncovered weight and another for the total description length. A lower cutoff on vertex weights sets the block size: larger blocks save seeds, and the cutoff keeps the necessary counting precision inverse polynomial. The construction uses O ( n / log n ) O(n/\log n) O ( n / log n ) blocks. Their seed and length fields therefore cost O L ( n ) O_L(n) O L ( n ) bits altogether. The decoder evaluates only the resulting short descriptions (Section 5).
Why the lower bound survives adaptive queries
Partition the vertices into 2 m 2^m 2 m buckets. Each contains a hidden vertex with a fair membership bit. Finding such a vertex in another bucket means locating its ( n − m ) (n-m) ( n − m ) -bit suffix. An input’s label can remain ambiguous until it has been compared to several other hidden vertices. For ordinary advice, amplification reuses the word and forces the cost up to m ( n − m ) − O q ( n log n ) m(n-m)-O_q(n\log n) m ( n − m ) − O q ( n log n ) bits. The balanced choice m = ⌊ n / 2 ⌋ m=\lfloor n/2\rfloor m = ⌊ n /2 ⌋ recovers the quarter.
An off-cube query may involve every entry of the table. We identify the Boolean positions at which changing one entry can affect the likelihood of its transcript. A degree-two polynomial that vanishes at all query points can mask the change at every other position. Factoring such a polynomial across the two endpoints of an edge shows that the transcript of q q q queries can address at most 2 q 2q 2 q vertices. There is also a stronger conclusion across successive runs on the same oracle. If the earlier runs never addressed the current input, any newly visible edge from it must have its other endpoint addressed by the current run alone. This is the step that permits an error count across inputs despite the shared extension.
Open problems. The unconditional lower bounds concern access to a selector table and relativized languages. Without hypotheses, the ordinary advice complexity of P-selective languages with polynomial-time decoding remains between n + 1 n+1 n + 1 bits, forced by [12 ] , and n 2 − n log 2 n + O ( n ) n^2-n\log_2 n+O(n) n 2 − n log 2 n + O ( n ) . Theorem 1.5 shows that closing the gap below n 2 / 4 n^2/4 n 2 /4 , even under H, requires a nonrelativizing argument. It is also open whether H can be replaced by a weaker derandomization hypothesis, for instance one that only fools nondeterministic circuits of a fixed polynomial size.
Counting covering tuples
Orient the side to be recognized so that it beats its complement, reversing all comparisons if needed. An anchor a a a on this side certifies x x x when x = a x=a x = a or x ≻ a x \succ a x ≻ a . A list covers the side when it certifies each of its vertices. Checking a cover takes one nonadaptive comparison per anchor. All logarithms are base two except where ln is written.
We first give the fixed-point argument in a form that also applies to payoff deviations in games. The exponent is a variable in the fixed point. This allows the scores to exceed one before normalization.
Lemma 2.1 (Normalizing a family of scores). Let p ↦ ( g i ( p ) ) i = 1 N p \mapsto(g_i(p))_{i=1}^{N} p ↦ ( g i ( p ) ) i = 1 N be continuous on the probability simplex. Suppose that the scores are positive on a common nonempty set of indices, zero elsewhere, and that ∑ i p i g i ( p ) ≤ 2 − c \sum_i p_i g_i(p) \le2^{-c} ∑ i p i g i ( p ) ≤ 2 − c for every p p p , for some c > 0 c > 0 c > 0 . Given 0 < ζ < 1 0 < \zeta< 1 0 < ζ < 1 , there are a distribution p p p and a real 0 < J ≤ log 2 ( N / ζ ) / c 0 < J \le\log_2(N/\zeta)/c 0 < J ≤ log 2 ( N / ζ ) / c satisfying
∑ i g i ( p ) J = ζ , p i = g i ( p ) J / ζ , ∑ i p i 1 + 1 / J ≤ ζ − 1 / J 2 − c . \sum_i g_i(p)^J = \zeta,\qquad p_i = g_i(p)^J/\zeta,\qquad\sum_i p_i^{1+1/J} \le\zeta^{-1/J}2^{-c}. i ∑ g i ( p ) J = ζ , p i = g i ( p ) J / ζ , i ∑ p i 1 + 1/ J ≤ ζ − 1/ J 2 − c . In particular every score at this distribution is less than one.
Proof. Restrict to the face supported on the positive indices, whose number is M ≥ 1 M \ge1 M ≥ 1 . Put Z ( p , J ) = ∑ i g i ( p ) J Z(p,J) = \sum_i g_i(p)^J Z ( p , J ) = ∑ i g i ( p ) J on this face, summing over those indices. Choose U > log 2 ( N / ζ ) / c U > \log_2(N/\zeta)/c U > log 2 ( N / ζ ) / c . On the product of the face with [ 0 , U ] [0,U] [ 0 , U ] apply Brouwer’s theorem to the continuous map
( p , J ) ⟼ ( ( g i ( p ) J / Z ( p , J ) ) i , proj [ 0 , U ] ( J + log 2 ( Z ( p , J ) / ζ ) ) ) . (p,J) \longmapsto\left((g_i(p)^J/Z(p,J))_i,\ \operatorname{proj}_{[0,U]}\left(J+\log_2(Z(p,J)/\zeta)\right)\right). ( p , J ) ⟼ ( ( g i ( p ) J / Z ( p , J ) ) i , proj [ 0 , U ] ( J + log 2 ( Z ( p , J ) / ζ ) ) ) .
At J = 0 J = 0 J = 0 the sum is M > ζ M > \zeta M > ζ , so a fixed point cannot lie at this endpoint. Whenever J > 0 J > 0 J > 0 and the first coordinate is fixed, convexity gives
N − 1 / J ≤ ∑ i p i 1 + 1 / J = Z ( p , J ) − 1 / J ∑ i p i g i ( p ) ≤ Z ( p , J ) − 1 / J 2 − c . N^{-1/J} \le\sum_i p_i^{1+1/J} = Z(p,J)^{-1/J}\sum_i p_i g_i(p) \le Z(p,J)^{-1/J}2^{-c}. N − 1/ J ≤ i ∑ p i 1 + 1/ J = Z ( p , J ) − 1/ J i ∑ p i g i ( p ) ≤ Z ( p , J ) − 1/ J 2 − c .
This forces Z ( p , U ) < ζ Z(p,U) < \zeta Z ( p , U ) < ζ at a fixed first coordinate and excludes the upper endpoint. The second coordinate at an interior fixed point forces Z = ζ Z = \zeta Z = ζ . The same inequality proves both remaining bounds.
Lemma 2.2 (A self-consistent distribution of anchors). Let S S S be a tournament on K ≥ 2 K \ge2 K ≥ 2 vertices, with uniform distribution U U U . Fix 0 < ϵ ≤ 1 / 2 0 < \epsilon\le1/2 0 < ϵ ≤ 1/2 and 0 < ζ < 1 0 < \zeta< 1 0 < ζ < 1 . There are a distribution p p p on S S S and a real J > 0 J > 0 J > 0 such that, for ν = ( 1 − ϵ ) p + ϵ U \nu= (1-\epsilon)p+\epsilon U ν = ( 1 − ϵ ) p + ϵ U and s ( x ) = Pr a ∼ ν [ a ≻ x ] s(x) = \Pr_{a\sim\nu}[a \succ x] s ( x ) = Pr a ∼ ν [ a ≻ x ] ,
∑ x s ( x ) J = ζ , p ( x ) = s ( x ) J / ζ . \sum_x s(x)^J = \zeta,\qquad p(x) = s(x)^J/\zeta. x ∑ s ( x ) J = ζ , p ( x ) = s ( x ) J / ζ . Their power moment A = ∑ x ν ( x ) 1 + 1 / J A = \sum_x \nu(x)^{1+1/J} A = ∑ x ν ( x ) 1 + 1/ J satisfies
A ≤ 1 2 ζ − 1 / J ( 1 + 2 ϵ ) , J ≤ log ( K / ζ ) log ( 2 / ( 1 + ϵ ) ) . A \le\frac{1}{2}\zeta^{-1/J}(1+2\epsilon),\qquad J \le\frac{\log(K/\zeta)}{\log(2/(1+\epsilon))}. A ≤ 2 1 ζ − 1/ J ( 1 + 2 ϵ ) , J ≤ log ( 2/ ( 1 + ϵ )) log ( K / ζ ) . Furthermore ( ϵ / 4 ) J ≤ 4 ζ / K (\epsilon/4)^J \le4\zeta/K ( ϵ /4 ) J ≤ 4 ζ / K .
Proof. Given u u u , let g x ( u ) g_x(u) g x ( u ) be the miss probability under ( 1 − ϵ ) u + ϵ U (1-\epsilon)u+\epsilon U ( 1 − ϵ ) u + ϵ U . Its positive coordinates are exactly the vertices of positive indegree, regardless of u u u . For independent x , a ∼ u x,a\sim u x , a ∼ u , the probability that a ≻ x a \succ x a ≻ x is ( 1 − ∑ x u ( x ) 2 ) / 2 (1-\sum_x u(x)^2)/2 ( 1 − ∑ x u ( x ) 2 ) /2 . Consequently ∑ x u ( x ) g x ( u ) ≤ ( 1 + ϵ ) / 2 \sum_x u(x)g_x(u) \le(1+\epsilon)/2 ∑ x u ( x ) g x ( u ) ≤ ( 1 + ϵ ) /2 . Apply Lemma 2.1 with 2 − c = ( 1 + ϵ ) / 2 2^{-c} = (1+\epsilon)/2 2 − c = ( 1 + ϵ ) /2 . It gives the stated normalization and the bound on J J J . Convexity gives
A ≤ ( 1 − ϵ ) ∑ x p ( x ) 1 + 1 / J + ϵ K − 1 / J ≤ ( 1 − ϵ ) ζ − 1 / J ( 1 + ϵ ) / 2 + ϵ K − 1 / J ≤ 1 2 ζ − 1 / J ( 1 + 2 ϵ ) . A \le(1-\epsilon)\sum_x p(x)^{1+1/J}+\epsilon K^{-1/J} \le(1-\epsilon)\zeta^{-1/J}(1+\epsilon)/2+\epsilon K^{-1/J} \le\frac{1}{2}\zeta^{-1/J}(1+2\epsilon). A ≤ ( 1 − ϵ ) x ∑ p ( x ) 1 + 1/ J + ϵ K − 1/ J ≤ ( 1 − ϵ ) ζ − 1/ J ( 1 + ϵ ) /2 + ϵ K − 1/ J ≤ 2 1 ζ − 1/ J ( 1 + 2 ϵ ) .
Finally, if b > 0 b > 0 b > 0 vertices have indegree less than K / 4 K/4 K /4 , their mean indegree in the induced tournament is ( b − 1 ) / 2 < K / 4 (b-1)/2 < K/4 ( b − 1 ) /2 < K /4 . At least K / 4 K/4 K /4 vertices therefore have indegree at least K / 4 K/4 K /4 (also directly for K = 2 , 3 K=2,3 K = 2 , 3 ). For each of them s ( x ) ≥ ϵ / 4 s(x) \ge\epsilon/4 s ( x ) ≥ ϵ /4 .
Theorem 2.3 (A universal codebook). A single computable decoder recognizes every legal selector cut on n n n -bit strings with zero error using n 2 / 4 + O ( n ) n^2/4+O(n) n 2 /4 + O ( n ) ordinary advice bits and at most n n n nonadaptive Boolean comparisons. More generally, suppose that a cover of a specified K K K -vertex subtournament suffices to recognize the cut. With v = log K v=\log K v = log K and u = min { v , n / 2 } u=\min\{v,n/2\} u = min { v , n /2 } , the decoder uses u ( n − u ) + O ( n ) u(n-u)+O(n) u ( n − u ) + O ( n ) advice bits and at most ⌈ v ⌉ + 1 \lceil v\rceil+1 ⌈ v ⌉ + 1 comparisons.
Proof. Write S S S for the side to be covered, reversing the orientation if necessary. Assume K ≥ 2 K\ge2 K ≥ 2 . Apply Lemma 2.2 with ϵ = 1 / ( 32 n ) \epsilon=1/(32n) ϵ = 1/ ( 32 n ) and ζ = 2 / 3 \zeta=2/3 ζ = 2/3 , and put r = ⌈ J ⌉ r=\lceil J\rceil r = ⌈ J ⌉ . Since ( v + 1 ) log ( 1 + 1 / ( 32 n ) ) < log ( 4 / 3 ) (v+1)\log(1+1/(32n))<\log(4/3) ( v + 1 ) log ( 1 + 1/ ( 32 n )) < log ( 4/3 ) for v ≤ n v\le n v ≤ n , the lemma gives J < v + 1 J<v+1 J < v + 1 and r ≤ ⌈ v ⌉ + 1 r\le\lceil v\rceil+1 r ≤ ⌈ v ⌉ + 1 . Also J ϵ = O ( 1 ) J\epsilon=O(1) J ϵ = O ( 1 ) , so its power-moment bound gives − J log A ≥ J − O ( 1 ) -J\log A\ge J-O(1) − J log A ≥ J − O ( 1 ) .
Let π = ν ⊗ r \pi=\nu^{\otimes r} π = ν ⊗ r and let C \mathcal{C} C be its covering tuples. A union bound gives π ( C ) ≥ 1 − ∑ x s ( x ) r ≥ 1 / 3 \pi(\mathcal{C})\ge1-\sum_x s(x)^r\ge1/3 π ( C ) ≥ 1 − ∑ x s ( x ) r ≥ 1/3 . Hölder’s inequality applied to the restriction of π \pi π to C \mathcal{C} C yields
∣ C ∣ ≥ π ( C ) J + 1 ( ∑ t ∈ S r π ( t ) 1 + 1 / J ) J ≥ ( 1 / 3 ) J + 1 A − r J ≥ 2 r 2 − O ( r + 1 ) . |\mathcal{C}|\ge\frac{\pi(\mathcal{C})^{J+1}}{\left(\sum_{t\in S^r}\pi(t)^{1+1/J}\right)^J}\ge(1/3)^{J+1}A^{-rJ}\ge2^{r^2-O(r+1)}. ∣ C ∣ ≥ ( ∑ t ∈ S r π ( t ) 1 + 1/ J ) J π ( C ) J + 1 ≥ ( 1/3 ) J + 1 A − r J ≥ 2 r 2 − O ( r + 1 ) . For a singleton take r = 1 r=1 r = 1 . A uniform ambient tuple therefore covers S S S using anchors in S S S with probability at least 2 − r ( n − r ) − C ( r + 1 ) 2^{-r(n-r)-C(r+1)} 2 − r ( n − r ) − C ( r + 1 ) for one absolute integer C C C .
For each r ≤ n + 1 r\le n+1 r ≤ n + 1 sample a separate list of 2 2 n + max { 0 , r ( n − r ) + C ( r + 1 ) } 2^{2n+\max\{0,r(n-r)+C(r+1)\}} 2 2 n + m a x { 0 , r ( n − r ) + C ( r + 1 )} independent ambient tuples. For each marked tournament take a qualifying r r r . Its failure probability is at most exp ( − 2 2 n ) \exp(-2^{2n}) exp ( − 2 2 n ) . The number of tournaments with a marked vertex subset is at most 2 ( 2 n 2 ) + 2 n 2^{\binom{2^n}{2}+2^n} 2 ( 2 2 n ) + 2 n , so one choice of lists works for every marked tournament at once. The lexicographically first such family is computable by finite enumeration. For every nonempty marked subset verify that some list with r ≤ ⌈ log K ⌉ + 1 r\le\lceil\log K\rceil+1 r ≤ ⌈ log K ⌉ + 1 covers it using anchors in it. The decoder regenerates the indexed tuple and compares the input with these anchors in the indicated orientation. An advice flag handles an empty side. Apart from O ( n ) O(n) O ( n ) bits the index costs r ( n − r ) r(n-r) r ( n − r ) , bounded by u ( n − u ) + O ( n ) u(n-u)+O(n) u ( n − u ) + O ( n ) for r ≤ ⌈ v ⌉ + 1 r\le\lceil v\rceil+1 r ≤ ⌈ v ⌉ + 1 . For a nontrivial legal cut take the smaller side, for which K ≤ 2 n − 1 K\le2^{n-1} K ≤ 2 n − 1 and r ≤ n r\le n r ≤ n . The computation of the lists has unrestricted running time.
Oblivious search for an equilibrium
A symmetric constant-sum game is specified by an N N N -by-N N N matrix A ∈ [ 0 , 1 ] N × N A\in[0,1]^{N\times N} A ∈ [ 0 , 1 ] N × N with A i j + A j i = 1 A_{ij}+A_{ji}=1 A ij + A j i = 1 . On the action pair ( i , j ) (i,j) ( i , j ) the payoffs are ( A i j , A j i ) (A_{ij},A_{ji}) ( A ij , A j i ) . In particular A i i = 1 / 2 A_{ii}=1/2 A ii = 1/2 . Subtracting 1 / 2 1/2 1/2 from each payoff yields the equivalent zero-sum normalization. We use the ordinary additive ϵ \epsilon ϵ -Nash condition: neither player gains more than ϵ \epsilon ϵ by unilateral deviation. An oblivious procedure samples a pair of mixed strategies from a distribution that depends only on N N N and ϵ \epsilon ϵ . Let P ϵ ( N ) P_\epsilon(N) P ϵ ( N ) be the supremum over such distributions of the infimum, over games, of the probability of proposing an ϵ \epsilon ϵ -Nash equilibrium. Let L ϵ ( N ) L_\epsilon(N) L ϵ ( N ) be the minimum cardinality of a game-independent list of profiles containing an ϵ \epsilon ϵ -Nash equilibrium for every such game. All logarithms are to base two.
Theorem 3.1. Fix 0 < ϵ < 1 / 2 0<\epsilon<1/2 0 < ϵ < 1/2 , put n = log N n=\log N n = log N , β = 1 / 2 + ϵ \beta=1/2+\epsilon β = 1/2 + ϵ , and set
c = 1 − H 2 ( β ) = β log ( 2 β ) + ( 1 − β ) log ( 2 ( 1 − β ) ) . c=1-H_2(\beta)=\beta\log(2\beta)+(1-\beta)\log(2(1-\beta)). c = 1 − H 2 ( β ) = β log ( 2 β ) + ( 1 − β ) log ( 2 ( 1 − β )) . Then
n 2 4 c − O ϵ ( n log n ) ≤ − log P ϵ ( N ) ≤ log L ϵ ( N ) ≤ n 2 4 c + O ϵ ( n ) . \frac{n^2}{4c}-O_\epsilon(n\log n)\le-\log P_\epsilon(N)\le\log L_\epsilon(N)\le\frac{n^2}{4c}+O_\epsilon(n). 4 c n 2 − O ϵ ( n log n ) ≤ − log P ϵ ( N ) ≤ log L ϵ ( N ) ≤ 4 c n 2 + O ϵ ( n ) . A proposal attaining the upper bound on − log P ϵ ( N ) -\log P_\epsilon(N) − log P ϵ ( N ) chooses a length uniformly from 1 , … , ⌊ ( n + 1 ) / c ⌋ 1,\ldots,\lfloor(n+1)/c\rfloor 1 , … , ⌊( n + 1 ) / c ⌋ , draws that many independent uniform actions, and uses their empirical distribution for both players. The lower bound already holds when every off-diagonal payoff belongs to { 0 , 1 } \{0,1\} { 0 , 1 } , and allows arbitrary pairs of mixed strategies.
For a mixed strategy z z z define v A ( z ) = max i ( A z ) i v_A(z)=\max_i(Az)_i v A ( z ) = max i ( A z ) i . The profile ( z , z ) (z,z) ( z , z ) has expected payoff 1 / 2 1/2 1/2 for each player and is an ϵ \epsilon ϵ -Nash equilibrium exactly when v A ( z ) ≤ β v_A(z)\le\beta v A ( z ) ≤ β . The same test controls asymmetric proposals. If ( x , y ) (x,y) ( x , y ) is an ϵ \epsilon ϵ -Nash equilibrium and u = x T A y u=x^{\mathsf T}Ay u = x T A y , its two deviation constraints imply
v A ( y ) ≤ u + ϵ , v A ( x ) ≤ 1 − u + ϵ , v A ( ( x + y ) / 2 ) ≤ β . v_A(y)\le u+\epsilon,\qquad v_A(x)\le1-u+\epsilon,\qquad v_A((x+y)/2)\le\beta. v A ( y ) ≤ u + ϵ , v A ( x ) ≤ 1 − u + ϵ , v A (( x + y ) /2 ) ≤ β .
These implications use A + A T = 11 T A+A^{\mathsf T}=\mathbf{1}\mathbf{1}^{\mathsf T} A + A T = 1 1 T .
Lemma 3.2 (Counting empirical strategies). For every such A A A some integer 1 ≤ r ≤ ⌈ ( n + 1 ) / c ⌉ 1\le r\le\lceil(n+1)/c\rceil 1 ≤ r ≤ ⌈( n + 1 ) / c ⌉ has at least 2 c r 2 − ( c + 2 ) r − 1 2^{cr^2-(c+2)r-1} 2 c r 2 − ( c + 2 ) r − 1 ordered r r r -tuples of actions whose empirical strategy z z z satisfies v A ( z ) ≤ β v_A(z)\le\beta v A ( z ) ≤ β .
Proof. Let λ = log ( β / ( 1 − β ) ) > 0 \lambda=\log(\beta/(1-\beta))>0 λ = log ( β / ( 1 − β )) > 0 . For a distribution p p p on the actions define
q p ( i ) = 2 − λ β ( 1 + ( 2 λ − 1 ) ( A p ) i ) . q_p(i)=2^{-\lambda\beta}\left(1+(2^\lambda-1)(Ap)_i\right). q p ( i ) = 2 − λ β ( 1 + ( 2 λ − 1 ) ( A p ) i ) . Since p T A p = 1 / 2 p^{\mathsf T}Ap=1/2 p T A p = 1/2 , for every p p p we have
∑ i p i q p ( i ) = 2 − λ β ( 1 + 2 λ ) / 2 = 2 − c . \sum_i p_iq_p(i)=2^{-\lambda\beta}(1+2^\lambda)/2=2^{-c}. i ∑ p i q p ( i ) = 2 − λ β ( 1 + 2 λ ) /2 = 2 − c . Lemma 2.1 , with g i = q p ( i ) g_i=q_p(i) g i = q p ( i ) and ζ = 1 / 2 \zeta=1/2 ζ = 1/2 , gives p p p and 0 < J ≤ ( n + 1 ) / c 0<J\le(n+1)/c 0 < J ≤ ( n + 1 ) / c such that
∑ i q p ( i ) J = 1 / 2 , p i = 2 q p ( i ) J , ∑ i p i 1 + 1 / J = 2 1 / J − c . \sum_i q_p(i)^J=1/2,\qquad p_i=2q_p(i)^J,\qquad\sum_i p_i^{1+1/J}=2^{1/J-c}. i ∑ q p ( i ) J = 1/2 , p i = 2 q p ( i ) J , i ∑ p i 1 + 1/ J = 2 1/ J − c . The final equality uses the exact mean 2 − c 2^{-c} 2 − c above. At this p p p every q p ( i ) q_p(i) q p ( i ) is less than one, although the score of a profitable deviation can exceed one at other distributions. Set r = ⌈ J ⌉ r=\lceil J\rceil r = ⌈ J ⌉ . Sample a 1 , … , a r a_1,\ldots,a_r a 1 , … , a r independently from p p p . For any pure deviation i i i , convexity gives 2 λ u ≤ 1 + ( 2 λ − 1 ) u 2^{\lambda u}\le1+(2^\lambda-1)u 2 λ u ≤ 1 + ( 2 λ − 1 ) u for 0 ≤ u ≤ 1 0\le u\le1 0 ≤ u ≤ 1 . Exponential Markov and independence thus give
Pr [ 1 r ∑ j = 1 r A i a j > β ] ≤ q p ( i ) r . \Pr\left[\frac{1}{r}\sum_{j=1}^{r}A_{ia_j}>\beta\right]\le q_p(i)^r. Pr [ r 1 j = 1 ∑ r A i a j > β ] ≤ q p ( i ) r . Summing over i i i bounds the failure probability by Z = 1 / 2 Z=1/2 Z = 1/2 . Let C C C be the good ordered tuples and μ = p ⊗ r \mu=p^{\otimes r} μ = p ⊗ r . Hölder’s inequality yields
∣ C ∣ ≥ μ ( C ) J + 1 ( ∑ a μ ( a ) 1 + 1 / J ) J ≥ 2 c r J − r − J − 1 ≥ 2 c r 2 − ( c + 2 ) r − 1 . |C|\ge\frac{\mu(C)^{J+1}}{\left(\sum_a\mu(a)^{1+1/J}\right)^J}\ge2^{crJ-r-J-1}\ge2^{cr^2-(c+2)r-1}. ∣ C ∣ ≥ ( ∑ a μ ( a ) 1 + 1/ J ) J μ ( C ) J + 1 ≥ 2 cr J − r − J − 1 ≥ 2 c r 2 − ( c + 2 ) r − 1 .
Upper bounds in Theorem 3.1 . For the length in Lemma 3.2, a uniform ambient tuple is good with probability at least 2 − r ( n − c r ) − O ( r + 1 ) 2^{-r(n-cr)-O(r+1)} 2 − r ( n − cr ) − O ( r + 1 ) . Since r ( n − c r ) ≤ n 2 / ( 4 c ) r(n-cr)\le n^2/(4c) r ( n − cr ) ≤ n 2 / ( 4 c ) and r = O ϵ ( n + 1 ) r=O_\epsilon(n+1) r = O ϵ ( n + 1 ) , sampling the length as well gives success at least 2 − n 2 / ( 4 c ) − O ϵ ( n ) 2^{-n^2/(4c)-O_\epsilon(n)} 2 − n 2 / ( 4 c ) − O ϵ ( n ) . An explicit payoff matrix permits verification of a symmetric proposal in O ( N r ) O(Nr) O ( N r ) arithmetic operations.
For a finite list that works for every real payoff matrix, take an even integer D = 2 ⌈ n ⌉ D=2\lceil n\rceil D = 2 ⌈ n ⌉ and use ϵ ′ = ϵ − 1 / D \epsilon'=\epsilon-1/D ϵ ′ = ϵ − 1/ D , positive for all sufficiently large N N N . Round each game on unordered pairs to a complementary pair of multiples of 1 / D 1/D 1/ D , giving entrywise error at most 1 / D 1/D 1/ D and preserving the diagonal. There are at most G = ( D + 1 ) N ( N − 1 ) / 2 G=(D+1)^{N(N-1)/2} G = ( D + 1 ) N ( N − 1 ) /2 rounded games. Let p ∗ p_* p ∗ be the guaranteed success of the sampler above for ϵ ′ \epsilon' ϵ ′ . The constants in its estimate are bounded uniformly for ϵ ′ ∈ [ ϵ / 2 , ϵ ] \epsilon'\in[\epsilon/2,\epsilon] ϵ ′ ∈ [ ϵ /2 , ϵ ] by the displayed finite counting lemma. Smoothness of 1 / c 1/c 1/ c on this interval gives − log p ∗ ≤ n 2 / ( 4 c ) + O ϵ ( n ) -\log p_*\le n^2/(4c)+O_\epsilon(n) − log p ∗ ≤ n 2 / ( 4 c ) + O ϵ ( n ) . A list of ⌈ ( ln G + 1 ) / p ∗ ⌉ \lceil(\ln G+1)/p_*\rceil ⌈( ln G + 1 ) / p ∗ ⌉ independent proposals works for every rounded game with positive probability. Any successful symmetric proposal has v A ( z ) ≤ 1 / 2 + ϵ v_A(z)\le1/2+\epsilon v A ( z ) ≤ 1/2 + ϵ in the original game. The covering list adds O ( n ) O(n) O ( n ) to the log size. Finally, uniform sampling from any universal list gives P ϵ ( N ) ≥ 1 / L ϵ ( N ) P_\epsilon(N)\ge1/L_\epsilon(N) P ϵ ( N ) ≥ 1/ L ϵ ( N ) .
The converse is proved in Theorem A.1 . The hard tournament has one distinguished action per bucket. To be secure, a proposed strategy must locate enough of these actions to prevent a fresh core row from winning too much of its mass. A weighted binomial estimate handles proposals with unequal weights.
Corollary 3.3 (Correlated proposals). The same bounds hold for obliviously proposing a coarse correlated equilibrium of additive error ϵ \epsilon ϵ , and for a correlated equilibrium with maximum expected gain at most ϵ \epsilon ϵ under a swap of the recommended action.
Proof. Let an arbitrary joint proposal have marginals x , y x,y x , y , and let the row player’s expected payoff be u u u . The two coarse deviation inequalities again give v A ( y ) ≤ u + ϵ v_A(y) \le u+\epsilon v A ( y ) ≤ u + ϵ and v A ( x ) ≤ 1 − u + ϵ v_A(x) \le1-u+\epsilon v A ( x ) ≤ 1 − u + ϵ . Thus such a proposal yields an ϵ \epsilon ϵ -secure ( x + y ) / 2 (x+y)/2 ( x + y ) /2 by a game-independent map. For the converse, take the product z ⊗ z z\otimes z z ⊗ z of an ϵ \epsilon ϵ -secure strategy with itself. The opponent’s action is independent of one’s recommendation, so the best swap rule earns at most v A ( z ) v_A(z) v A ( z ) . Following the recommendation earns 1 / 2 1/2 1/2 .
In a tournament game the entries of z z z can be interpreted as a lottery over alternatives in pairwise comparisons. Security means that no single alternative defeats this lottery with probability greater than 1 / 2 + ϵ 1/2+\epsilon 1/2 + ϵ . This is the approximate von Neumann winner criterion used in preference learning [7 ] .
Consequences for tournaments
The quarter in Theorem 2.3 is not specific to selectors. This section records three consequences of Lemma 2.2 for tournaments alone. A set D D D of vertices dominates a tournament if every vertex outside D D D is beaten by a member of D D D , and a tuple dominates if the set of its entries does. Reversing all edges turns dominating sets into the covers of § 2 , so Lemma 2.2 and Theorem 2.3 apply to the reversed tournament. Write γ ( T ) \gamma(T) γ ( T ) for the domination number of T T T .
Many dominating tuples
Corollary 4.1 (Many dominating tuples). Every tournament T T T on K ≥ 2 K \ge2 K ≥ 2 vertices has a distribution ν \nu ν on its vertices, a real J > 0 J>0 J > 0 and an integer r = ⌈ J ⌉ ≤ ⌈ log K ⌉ + 1 r=\lceil J\rceil\le\lceil\log K\rceil+1 r = ⌈ J ⌉ ≤ ⌈ log K ⌉ + 1 with the following properties: r r r independent samples from ν \nu ν dominate T T T with probability at least 1 / 3 1/3 1/3 , and the Rényi entropy of order 1 + 1 / J 1+1/J 1 + 1/ J of ν \nu ν is at least J − O ( 1 ) J-O(1) J − O ( 1 ) . In particular T T T has at least 2 r 2 − O ( r ) 2^{r^2-O(r)} 2 r 2 − O ( r ) dominating r r r -tuples, and r ≥ γ ( T ) r\ge\gamma(T) r ≥ γ ( T ) .
Proof. Apply Lemma 2.2 to the reversed tournament with ζ = 2 / 3 \zeta=2/3 ζ = 2/3 and ϵ = 1 / ( 32 ( ⌈ log K ⌉ + 1 ) ) \epsilon=1/(32(\lceil\log K\rceil+1)) ϵ = 1/ ( 32 (⌈ log K ⌉ + 1 )) , and argue as in the proof of Theorem 2.3 with ⌈ log K ⌉ \lceil\log K\rceil ⌈ log K ⌉ in place of n n n . The Rényi entropy of order 1 + 1 / J 1+1/J 1 + 1/ J is − J log A -J\log A − J log A . A dominating r r r -tuple exists, so r ≥ γ ( T ) r\ge\gamma(T) r ≥ γ ( T ) .
The count is not a consequence of the existence of one small dominating set. A tournament can have a unique minimum dominating set, and padding one dominating set of size γ \gamma γ with arbitrary vertices gives only about K r − γ K^{r-\gamma} K r − γ dominating r r r -tuples. For tournaments with γ ( T ) ≥ log K − 2 log log K − O ( 1 ) \gamma(T)\ge\log K-2\log\log K-O(1) γ ( T ) ≥ log K − 2 log log K − O ( 1 ) , which exist by Erdős’s argument [9 ] , padding at a scale r ≤ ⌈ log K ⌉ + 1 r\le\lceil\log K\rceil+1 r ≤ ⌈ log K ⌉ + 1 gives at most 2 O ( log K log log K ) 2^{O(\log K\log\log K)} 2 O ( l o g K l o g l o g K ) tuples, while Corollary 4.1 gives 2 r 2 − O ( r ) ≥ 2 2 log 2 K − O ( log K log log K ) 2^{r^2-O(r)}\ge2^{2\log^2 K-O(\log K\log\log K)} 2 r 2 − O ( r ) ≥ 2 2 l o g 2 K − O ( l o g K l o g l o g K ) .
Remark 4.2 (Why not a minimax strategy). An optimal strategy p ∗ p^* p ∗ of the symmetric zero-sum game on T T T is beaten by no vertex on average, so each vertex escapes a p ∗ p^* p ∗ -random dominator with probability at most 1 / 2 1/2 1/2 , and ⌈ log K ⌉ + 2 \lceil\log K\rceil+2 ⌈ log K ⌉ + 2 samples from p ∗ p^* p ∗ dominate with probability at least 3 / 4 3/4 3/4 .
Such a strategy can have very small support. Let A A A be a regular tournament on m = 2 ⌈ log K ⌉ + 1 m=2\lceil\log K\rceil+1 m = 2 ⌈ log K ⌉ + 1 vertices, and let B B B carry a uniformly random tournament on K − m K-m K − m further vertices, where each x ∈ B x\in B x ∈ B is beaten by an independent uniformly random set of ( m + 1 ) / 2 (m+1)/2 ( m + 1 ) /2 vertices of A A A and beats the rest. The uniform distribution on A A A is optimal, and its entropy is log log K + O ( 1 ) \log\log K+O(1) log log K + O ( 1 ) . A union bound over sets of size d = ⌊ 1 4 log 3 K ⌋ d=\lfloor\frac{1}{4}\log_3 K\rfloor d = ⌊ 4 1 log 3 K ⌋ shows that with high probability γ ( T ) > d \gamma(T)>d γ ( T ) > d : for each such set D D D , each x ∈ B ∖ D x\in B\setminus D x ∈ B ∖ D escapes D D D independently with probability at least 3 − d 3^{-d} 3 − d . So r r r samples from p ∗ p^* p ∗ produce at most m r = 2 O ( log K log log K ) m^r=2^{O(\log K\log\log K)} m r = 2 O ( l o g K l o g l o g K ) different tuples at a scale where Corollary 4.1 gives 2 Ω ( log 2 K ) 2^{\Omega(\log^2 K)} 2 Ω ( l o g 2 K ) . The finite exponent J J J in Lemma 2.2 is what forces the spread.
Random domination
How likely is a random set of t t t vertices to dominate an N N N -vertex tournament? A random tournament is dominated by a random set of size log N + O ( log log N ) \log N+O(\log\log N) log N + O ( log log N ) with high probability. The worst case is much smaller, and its exponent has the same form r ( L − r ) r(L-r) r ( L − r ) as the advice cost, with L = log ( N / t ) L=\log(N/t) L = log ( N / t ) in place of n n n .
Theorem 4.3 (Random domination). There is an absolute constant C C C with the following properties. Let N ≥ 2 N\ge2 N ≥ 2 and ⌈ log N ⌉ + 1 ≤ t ≤ N \lceil\log N\rceil+1\le t\le N ⌈ log N ⌉ + 1 ≤ t ≤ N , and put L = log ( N / t ) L=\log(N/t) L = log ( N / t ) .
In every tournament on N N N vertices, a uniformly random t t t -subset dominates with probability at least 2 − L 2 / 4 − C ( L + 1 ) log ( L + 2 ) 2^{-L^2/4-C(L+1)\log(L+2)} 2 − L 2 /4 − C ( L + 1 ) l o g ( L + 2 ) .
If L ≥ C L\ge C L ≥ C , some tournament on N N N vertices is dominated by a uniformly random t t t -subset with probability at most 2 − L 2 / 4 + C ( L + 1 ) log ( L + 2 ) 2^{-L^2/4+C(L+1)\log(L+2)} 2 − L 2 /4 + C ( L + 1 ) l o g ( L + 2 ) .
Proof. Sampling with replacement suffices. Draw t t t independent uniform vertices and complete the set of distinct draws by uniformly random new vertices to a t t t -set. The resulting distribution on t t t -sets is invariant under permutations of the vertices, hence uniform, and it contains the drawn set. Domination is monotone, so it suffices to bound the probability that the drawn set dominates. Let C 0 C_0 C 0 be the constant in the count 2 2 r 2 − C 0 r 2^{2r^2-C_0r} 2 2 r 2 − C 0 r of Corollary 4.1 .
Few samples. Suppose t < 4 ( ⌈ log N ⌉ + 2 ) t<4(\lceil\log N\rceil+2) t < 4 (⌈ log N ⌉ + 2 ) . The first r r r draws form a uniform r r r -tuple with r ≤ ⌈ log N ⌉ + 1 ≤ t r\le\lceil\log N\rceil+1\le t r ≤ ⌈ log N ⌉ + 1 ≤ t , so they dominate with probability at least
2 r 2 − C 0 r N r = 2 − r ( log N − r ) − C 0 r ≥ 2 − log 2 N / 4 − C 0 r . \frac{2^{r^2-C_0r}}{N^r}=2^{-r(\log N-r)-C_0r}\ge2^{-\log^2N/4-C_0r}. N r 2 r 2 − C 0 r = 2 − r ( l o g N − r ) − C 0 r ≥ 2 − l o g 2 N /4 − C 0 r .
Here log N = L + log t \log N=L+\log t log N = L + log t and log t = O ( log ( L + 2 ) ) \log t=O(\log(L+2)) log t = O ( log ( L + 2 )) : either log N < 64 \log N<64 log N < 64 and all quantities are bounded, or log ( 4 log N + 12 ) ≤ 1 2 log N \log(4\log N+12)\le\frac{1}{2}\log N log ( 4 log N + 12 ) ≤ 2 1 log N , whence log N ≤ 2 L \log N\le2L log N ≤ 2 L . So log 2 N / 4 ≤ L 2 / 4 + O ( ( L + 1 ) log ( L + 2 ) ) \log^2N/4\le L^2/4+O((L+1)\log(L+2)) log 2 N /4 ≤ L 2 /4 + O (( L + 1 ) log ( L + 2 )) .
Many samples. Suppose t ≥ 4 ( ⌈ log N ⌉ + 2 ) t\ge4(\lceil\log N\rceil+2) t ≥ 4 (⌈ log N ⌉ + 2 ) . Split the draws into a first half of t 1 = ⌊ t / 2 ⌋ ≥ 2 t / 5 t_1=\lfloor t/2\rfloor\ge2t/5 t 1 = ⌊ t /2 ⌋ ≥ 2 t /5 and a second half of t 2 = ⌈ t / 2 ⌉ t_2=\lceil t/2\rceil t 2 = ⌈ t /2 ⌉ . Let S ′ S' S ′ be the set of vertices that are neither drawn in the first half nor beaten by a first-half draw. A vertex x x x with d − ( x ) d^-(x) d − ( x ) in-neighbours lies in S ′ S' S ′ with probability at most exp ( − t 1 ( d − ( x ) + 1 ) / N ) \exp(-t_1(d^-(x)+1)/N) exp ( − t 1 ( d − ( x ) + 1 ) / N ) . The k k k vertices of smallest in-degree span a tournament with average in-degree ( k − 1 ) / 2 (k-1)/2 ( k − 1 ) /2 , so the k k k -th smallest in-degree is at least ( k − 1 ) / 2 (k-1)/2 ( k − 1 ) /2 , and
E ∣ S ′ ∣ ≤ ∑ k ≥ 1 exp ( − t 1 ( k + 1 ) 2 N ) ≤ 2 N t 1 ≤ 5 N t . \mathbb{E}|S'|\le\sum_{k\ge1}\exp\left(-\frac{t_1(k+1)}{2N}\right)\le\frac{2N}{t_1}\le\frac{5N}{t}. E ∣ S ′ ∣ ≤ k ≥ 1 ∑ exp ( − 2 N t 1 ( k + 1 ) ) ≤ t 1 2 N ≤ t 5 N .
By Markov’s inequality K ′ = ∣ S ′ ∣ ≤ 10 N / t K'=|S'|\le10N/t K ′ = ∣ S ′ ∣ ≤ 10 N / t with probability at least $1/2$. Fix such a first half. If K ′ = 0 K'=0 K ′ = 0 the first half dominates. Otherwise Corollary 4.1 applied to the subtournament on S ′ S' S ′ (trivially when K ′ = 1 K'=1 K ′ = 1 ) gives r ′ ≤ log K ′ + 2 ≤ L + 6 r'\le\log K'+2\le L+6 r ′ ≤ log K ′ + 2 ≤ L + 6 and at least 2 r ′ 2 − C 0 r ′ 2^{r'^2-C_0r'} 2 r ′2 − C 0 r ′ dominating r ′ r' r ′ -tuples of S ′ S' S ′ . Every vertex outside S ′ S' S ′ is drawn or beaten in the first half, so the draws dominate T T T whenever the second half contains a dominating tuple of the subtournament on S ′ S' S ′ . Let X X X be the number of second-half draws in S ′ S' S ′ ; it is binomial with parameters t 2 t_2 t 2 and q = K ′ / N q=K'/N q = K ′ / N . Given X ≥ r ′ X\ge r' X ≥ r ′ , the first $r' of them are independent and uniform on S ′ S' S ′ , so they dominate the subtournament with probability at least 2 − r ′ ( log K ′ − r ′ ) − C 0 r ′ 2^{-r'(\log K'-r')-C_0r'} 2 − r ′ ( l o g K ′ − r ′ ) − C 0 r ′ .
If t 2 q ≥ r ′ t_2q \ge r' t 2 q ≥ r ′ , the median of X X X is at least r ′ r' r ′ , and the overall probability is at least
1 4 2 − r ′ ( log K ′ − r ′ ) − C 0 r ′ ≥ 2 − ( L + 4 ) 2 / 4 − O ( L + 1 ) . \frac{1}{4}2^{-r'(\log K'-r')-C_0r'} \ge2^{-(L+4)^2/4-O(L+1)}. 4 1 2 − r ′ ( l o g K ′ − r ′ ) − C 0 r ′ ≥ 2 − ( L + 4 ) 2 /4 − O ( L + 1 ) .
Otherwise q < r ′ / t 2 ≤ 1 / 2 q < r'/t_2 \le1/2 q < r ′ / t 2 ≤ 1/2 , because r ′ ≤ log N + 2 r' \le\log N+2 r ′ ≤ log N + 2 and t 2 ≥ 2 ( log N + 2 ) t_2 \ge2(\log N+2) t 2 ≥ 2 ( log N + 2 ) . Then, using ( 1 − q ) t 2 ≥ e − 2 q t 2 (1-q)^{t_2} \ge e^{-2qt_2} ( 1 − q ) t 2 ≥ e − 2 q t 2 ,
Pr [ X ≥ r ′ ] ≥ ( t 2 r ′ ) q r ′ ( 1 − q ) t 2 ≥ ( t 2 q r ′ ) r ′ e − 2 r ′ . \Pr[X \ge r'] \ge\binom{t_2}{r'}q^{r'}(1-q)^{t_2} \ge\left(\frac{t_2q}{r'}\right)^{r'}e^{-2r'}. Pr [ X ≥ r ′ ] ≥ ( r ′ t 2 ) q r ′ ( 1 − q ) t 2 ≥ ( r ′ t 2 q ) r ′ e − 2 r ′ .
and the product with the previous bound is at least
( t 2 K ′ N r ′ ) r ′ 2 − r ′ log K ′ + r ′ 2 − O ( r ′ ) = 2 − r ′ ( log ( N / t 2 ) − r ′ ) − r ′ log r ′ − O ( r ′ ) ≥ 2 − ( L + 1 ) 2 / 4 − O ( ( L + 1 ) log ( L + 2 ) ) , \left(\frac{t_2K'}{Nr'}\right)^{r'}2^{-r'\log K'+r'^2-O(r')} = 2^{-r'(\log(N/t_2)-r')-r'\log r'-O(r')} \ge2^{-(L+1)^2/4-O((L+1)\log(L+2))}, ( N r ′ t 2 K ′ ) r ′ 2 − r ′ l o g K ′ + r ′2 − O ( r ′ ) = 2 − r ′ ( l o g ( N / t 2 ) − r ′ ) − r ′ l o g r ′ − O ( r ′ ) ≥ 2 − ( L + 1 ) 2 /4 − O (( L + 1 ) l o g ( L + 2 )) ,
since log ( N / t 2 ) ≤ L + 1 \log(N/t_2) \le L+1 log ( N / t 2 ) ≤ L + 1 and r ′ ≤ L + 6 r' \le L+6 r ′ ≤ L + 6 . The factor K ′ K' K ′ cancels. Multiplying by 1 / 2 1/2 1/2 for the first half proves the first assertion.
The construction. Let m = ⌊ L / 2 ⌋ m=\lfloor L/2\rfloor m = ⌊ L /2 ⌋ , K = 2 m ≤ N K=2^m \le N K = 2 m ≤ N and d = ⌊ m − 2 log m ⌋ d=\lfloor m-2\log m\rfloor d = ⌊ m − 2 log m ⌋ . A uniformly random tournament T 0 T_0 T 0 on K K K vertices has γ ( T 0 ) ≥ d \gamma(T_0)\ge d γ ( T 0 ) ≥ d with positive probability [9 ] : for s = d − 1 s=d-1 s = d − 1 the expected number of dominating s s s -sets is at most K s exp ( − ( K − s ) 2 − s ) ≤ 2 m 2 e − m 2 < 1 K^s\exp(-(K-s)2^{-s}) \le2^{m^2}e^{-m^2}<1 K s exp ( − ( K − s ) 2 − s ) ≤ 2 m 2 e − m 2 < 1 , since ( K − s ) 2 − s ≥ ( K / 2 ) ⋅ 2 m 2 / K (K-s)2^{-s}\ge(K/2)\cdot2^{m^2}/K ( K − s ) 2 − s ≥ ( K /2 ) ⋅ 2 m 2 / K . Place such a T 0 T_0 T 0 on a set C C C of K K K vertices, let every vertex of C C C beat every vertex outside C C C , and orient the remaining edges arbitrarily. Only vertices of C C C beat vertices of C C C , so every dominating set D D D meets C C C in a dominating set of T 0 T_0 T 0 , and ∣ D ∩ C ∣ ≥ d |D\cap C|\ge d ∣ D ∩ C ∣ ≥ d . A fixed d d d -set lies in a uniform t t t -subset with probability at most ( t / N ) d (t/N)^d ( t / N ) d , so
Pr [ ∣ D ∩ C ∣ ≥ d ] ≤ ( K d ) ( t N ) d ≤ ( K t N ) d = 2 − d ( L − m ) . \Pr[|D\cap C|\ge d]\le\binom{K}{d}\left(\frac{t}{N}\right)^d\le\left(\frac{Kt}{N}\right)^d=2^{-d(L-m)}. Pr [ ∣ D ∩ C ∣ ≥ d ] ≤ ( d K ) ( N t ) d ≤ ( N K t ) d = 2 − d ( L − m ) .
Finally d ( L − m ) ≥ m ( L − m ) − ( 2 log m + 1 ) L ≥ L 2 / 4 − 1 / 4 − ( 2 log L + 1 ) L d(L-m)\ge m(L-m)-(2\log m+1)L\ge L^2/4-1/4-(2\log L+1)L d ( L − m ) ≥ m ( L − m ) − ( 2 log m + 1 ) L ≥ L 2 /4 − 1/4 − ( 2 log L + 1 ) L .
The same two estimates determine the size of universal families. Let U ( N , t ) U(N,t) U ( N , t ) be the least number of t t t -subsets of an N N N -set such that every tournament on it is dominated by one of them.
Corollary 4.4 (Universal dominating families). *Under the assumptions of Theorem 4.3, with L ≥ C L\ge C L ≥ C ,
L 2 4 − C ( L + 1 ) log ( L + 2 ) ≤ log U ( N , t ) ≤ L 2 4 + C ( L + 1 ) log ( L + 2 ) + 2 log N . \frac{L^2}{4}-C(L+1)\log(L+2)\le\log U(N,t)\le\frac{L^2}{4}+C(L+1)\log(L+2)+2\log N. 4 L 2 − C ( L + 1 ) log ( L + 2 ) ≤ log U ( N , t ) ≤ 4 L 2 + C ( L + 1 ) log ( L + 2 ) + 2 log N . Proof. For the upper bound take N 2 2 L 2 / 4 + C ( L + 1 ) log ( L + 2 ) N^2 2^{L^2/4+C(L+1)\log(L+2)} N 2 2 L 2 /4 + C ( L + 1 ) l o g ( L + 2 ) independent uniform t t t -subsets. A fixed tournament is missed by all of them with probability at most e − N 2 e^{-N^2} e − N 2 , and there are fewer than e N 2 e^{N^2} e N 2 tournaments. For the lower bound place the construction of Theorem 4.3 on a uniformly random K K K -set C C C . A fixed t t t -set F F F meets C C C in at least d d d vertices with probability at most ( K d ) ( K / N ) d ≤ 2 − d ( L − m ) \binom{K}{d}(K/N)^d\le2^{-d(L-m)} ( d K ) ( K / N ) d ≤ 2 − d ( L − m ) , so fewer than 2 d ( L − m ) 2^{d(L-m)} 2 d ( L − m ) sets miss some placement.
The upper bound is dominated by the term L 2 / 4 L^2/4 L 2 /4 once L ≫ log N L\gg\sqrt{\log N} L ≫ log N , for instance for every t ≤ N 1 − δ t\le N^{1-\delta} t ≤ N 1 − δ with δ > 0 \delta>0 δ > 0 fixed.
Description length of dominating sets
Every tournament on { 0 , 1 } n \{0,1\}^{n} { 0 , 1 } n has a dominating set of at most n + 1 n+1 n + 1 vertices, which takes about n 2 n^{2} n 2 bits to write down. Write C ( D ∣ n ) C(D\mid n) C ( D ∣ n ) for the Kolmogorov complexity of a set D D D , given n n n and encoded as a sorted list.
Theorem 4.5 (Describing dominating sets).
Every tournament on { 0 , 1 } n \{0,1\}^{n} { 0 , 1 } n has a dominating set D D D of at most n + 1 n+1 n + 1 vertices with C ( D ∣ n ) ≤ n 2 / 4 + O ( n ) C(D\mid n)\le n^{2}/4+O(n) C ( D ∣ n ) ≤ n 2 /4 + O ( n ) .
For all large n n n and every s ≥ 1 s\ge1 s ≥ 1 there is a tournament on { 0 , 1 } n \{0,1\}^{n} { 0 , 1 } n in which every dominating set D D D with ∣ D ∣ ≤ s |D|\le s ∣ D ∣ ≤ s satisfies C ( D ∣ n ) ≥ n 2 / 4 − n 2 log s − O ( n log n ) C(D\mid n)\ge n^{2}/4-\frac{n}{2}\log s-O(n\log n) C ( D ∣ n ) ≥ n 2 /4 − 2 n log s − O ( n log n ) . For ∣ D ∣ |D| ∣ D ∣ bounded by a polynomial in n n n , this is n 2 / 4 − O ( n log n ) n^{2}/4-O(n\log n) n 2 /4 − O ( n log n ) .
Proof. For the first part, the lists in the proof of Theorem 2.3 are computable from n n n and contain, for every tournament and every nonempty vertex set, a covering tuple of length r ≤ n + 1 r\le n+1 r ≤ n + 1 inside that set. Apply this to the reversed tournament and the whole vertex set. The index of the tuple, together with r r r , costs r ( n − r ) + O ( n ) ≤ n 2 / 4 + O ( n ) r(n-r)+O(n)\le n^{2}/4+O(n) r ( n − r ) + O ( n ) ≤ n 2 /4 + O ( n ) bits, and a fixed program prints the tuple from it.
For the second part let m = ⌊ n / 2 ⌋ m=\lfloor n/2\rfloor m = ⌊ n /2 ⌋ , K = 2 m K=2^{m} K = 2 m and d = ⌊ m − 2 log m ⌋ d=\lfloor m-2\log m\rfloor d = ⌊ m − 2 log m ⌋ , and place the construction of Theorem 4.3 on a uniformly random K K K -set C C C . A fixed D D D with ∣ D ∣ ≤ s |D|\le s ∣ D ∣ ≤ s meets C C C in at least d d d vertices with probability at most ( s K / 2 n ) d = 2 − d ( n − m − log s ) (sK/2^{n})^{d}=2^{-d(n-m-\log s)} ( sK / 2 n ) d = 2 − d ( n − m − l o g s ) . Fewer than 2 b 2^{b} 2 b sets have C ( D ∣ n ) < b C(D\mid n)<b C ( D ∣ n ) < b . For b = d ( n − m − log s ) b=d(n-m-\log s) b = d ( n − m − log s ) some placement of C C C therefore meets none of them in d d d vertices, and then none of them dominates. Finally d ( n − m − log s ) ≥ n 2 / 4 − n 2 log s − ( 2 log n + 1 ) n − 1 d(n-m-\log s)\ge n^{2}/4-\frac{n}{2}\log s-(2\log n+1)n-1 d ( n − m − log s ) ≥ n 2 /4 − 2 n log s − ( 2 log n + 1 ) n − 1 .
The second part needs some bound on ∣ D ∣ |D| ∣ D ∣ : the whole vertex set dominates and has complexity O ( 1 ) O(1) O ( 1 ) given n n n .
Remark 4.6 (Time-bounded descriptions). For tournaments computed by circuits of polynomial size, the method of § 5 should give dominating sets whose polynomial-time-bounded complexity is n 2 / 4 + O ( n ) n^{2}/4+O(n) n 2 /4 + O ( n ) under H, with the constant depending on the circuit size. In this setting membership in the covered set is trivial. We have not written out the details. This differs from language compression [6 ] , which describes every element of a set A A A in about log ∣ A ∣ \log|A| log ∣ A ∣ bits: here one element of a sparse set of tuples is described in about log ( universe / ∣ A ∣ ) \log(\text{universe}/|A|) log ( universe /∣ A ∣ ) bits. A direct hashing-plus-generator argument for such a set, which is defined by a universal condition, would need hardness against circuits with Σ 2 p \Sigma_{2}^{p} Σ 2 p gates.
Other covering relations
Remark 4.7 (Other covering relations). The tournament enters the first two parts of Lemma 2.2 only through the identity Pr x , a ∼ p [ a ≻ x ] = ( 1 − ∑ x p ( x ) 2 ) / 2 \Pr_{x,a\sim p}[a\succ x]=(1-\sum_x p(x)^2)/2 Pr x , a ∼ p [ a ≻ x ] = ( 1 − ∑ x p ( x ) 2 ) /2 . Suppose instead that a finite set S S S carries a relation in which an anchor a a a may miss x x x , no anchor misses itself, and Pr x , a ∼ p [ a misses x ] ≤ θ \Pr_{x,a\sim p}[a\text{ misses }x]\le\theta Pr x , a ∼ p [ a misses x ] ≤ θ for every distribution p p p on S S S , where 1 / 2 ≤ θ < 1 1/2\le\theta<1 1/2 ≤ θ < 1 . The same proof gives J ≤ log ( ∣ S ∣ / log ( 1 / ( θ + ϵ ) ) ) J\le\log(|S|/\log(1/(\theta+\epsilon))) J ≤ log ( ∣ S ∣/ log ( 1/ ( θ + ϵ ))) and A ≤ ζ − 1 / J ( θ + 2 ϵ ) A\le\zeta^{-1/J}(\theta+2\epsilon) A ≤ ζ − 1/ J ( θ + 2 ϵ ) . With ϵ \epsilon ϵ a small multiple of β / log K \beta/\log K β / log K , where β = log ( 1 / θ ) \beta=\log(1/\theta) β = log ( 1/ θ ) , the count in Theorem 2.3 gives at least 2 β r 2 − O ( r ) 2^{\beta r^{2}-O(r)} 2 β r 2 − O ( r ) covering r r r -tuples for some r = O ( log K / β ) r=O(\log K/\beta) r = O ( log K / β ) .
For example, let G G G be an oriented graph on S S S with independence number α \alpha α , and say that a a a covers x x x when x = a x=a x = a or x → a x\to a x → a . A p p p -random anchor misses a p p p -random vertex with probability ( 1 − ∑ x p ( x ) 2 ) / 2 (1-\sum_x p(x)^2)/2 ( 1 − ∑ x p ( x ) 2 ) /2 plus the p ⊗ p p\otimes p p ⊗ p mass of the unordered nonadjacent pairs. The Motzkin–Straus theorem [19 ] bounds that mass by ( 1 − 1 / α ) / 2 (1-1/\alpha)/2 ( 1 − 1/ α ) /2 , so θ = 1 − 1 / ( 2 α ) \theta=1-1/(2\alpha) θ = 1 − 1/ ( 2 α ) works. Tournaments are the case α = 1 \alpha=1 α = 1 .
Polynomial-time decoding under circuit hardness
Let H H H assert that some function in E E E requires circuits of size 2 c ℓ 2^{c\ell} 2 c ℓ with SAT gates on all sufficiently large input lengths ℓ \ell ℓ , for a constant c > 0 c>0 c > 0 . Circuit size charges the query wires. All logarithms below are binary.
Theorem 5.1. Under H H H , every P-selective language has a deterministic polynomial-time interpreter with n 2 / 4 + O L ( n ) n^{2/4+O_L(n)} n 2/4 + O L ( n ) ordinary advice bits. If its smaller nonempty side has size K ≤ 2 m K \le2^m K ≤ 2 m for an integer 0 ≤ m ≤ n − 1 0 \le m \le n-1 0 ≤ m ≤ n − 1 , the interpreter uses at most m + 1 m+1 m + 1 nonadaptive selector comparisons. Its advice length is bounded by
max 1 ≤ r ≤ m + 1 r ( n − r ) + O L ( n ) . \max_{1\le r\le m+1} r(n-r)+O_L(n). 1 ≤ r ≤ m + 1 max r ( n − r ) + O L ( n ) .
Two facts about short descriptions. Orient the smaller side S S S so that it beats its complement. Membership in S S S has polynomial-size nondeterministic circuits. Take a vertex w ∈ S w\in S w ∈ S of maximum indegree within S S S . Each x ∈ S x\in S x ∈ S reaches w w w in at most two steps, since otherwise all inneighbors of w w w , together with w w w , beat x x x . No vertex outside S S S reaches w w w .
We use two facts about short descriptions of strings. In each statement the string to describe has length N N N , polynomially bounded in n n n , with N ≥ n N\ge n N ≥ n . Only the generator and affine map in the second tool are used by the reconstruction algorithm.
If Y a ⊆ { 0 , 1 } d Y_a\subseteq\{0,1\}^d Y a ⊆ { 0 , 1 } d is recognized nondeterministically on ( a , y ) (a,y) ( a , y ) by a polynomial-size circuit, d = poly ( n ) d=\operatorname{poly}(n) d = poly ( n ) , and 1 / η = poly ( n ) 1/\eta=\operatorname{poly}(n) 1/ η = poly ( n ) , a polynomial-size nondeterministic circuit accepts every a a a with ∣ Y a ∣ ≥ T |Y_a|\ge T ∣ Y a ∣ ≥ T and only a a a with ∣ Y a ∣ ≥ ( 1 − η ) T |Y_a|\ge(1-\eta)T ∣ Y a ∣ ≥ ( 1 − η ) T . For completeness, take j = ⌈ 3 / η ⌉ j=\lceil3/\eta\rceil j = ⌈ 3/ η ⌉ and b = ⌈ log ( T j ) ⌉ + 1 b=\lceil\log(T^j)\rceil+1 b = ⌈ log ( T j )⌉ + 1 for 1 ≤ T ≤ 2 d 1\le T\le2^d 1 ≤ T ≤ 2 d . A random pairwise independent hash of j j j -tuples into { 0 , 1 } b \{0,1\}^b { 0 , 1 } b hits a specified target on Y a j Y_a^j Y a j with probability at least 7 / 32 7/32 7/32 in the large case and at most 1 / 16 1/16 1/16 if ∣ Y a ∣ < ( 1 − η ) T |Y_a|<(1-\eta)T ∣ Y a ∣ < ( 1 − η ) T . For the lower bound, apply two-term inclusion–exclusion to T j T^j T j elements, whose expected number of hits is in ( 1 / 4 , 1 / 2 ] (1/4,1/2] ( 1/4 , 1/2 ] . For the upper bound use ( 1 − η ) j < 1 / 8 (1-\eta)^j<1/8 ( 1 − η ) j < 1/8 . Fix O ( N ) O(N) O ( N ) independent hashes so the fraction of hits, thresholded at 9 / 64 9/64 9/64 , separates these cases simultaneously for every N N N -bit a a a . Chernoff’s bound and a union bound ensure existence. A witness lists successful hashes, preimages and their membership witnesses. For T > 2 d T>2^d T > 2 d use a rejecting circuit. This is the nonuniform set lower-bound test of Goldwasser and Sipser [10 ] .
Under H H H , suppose W ≠ ∅ W\ne\varnothing W = ∅ is contained in the acceptance set W ′ ⊆ { 0 , 1 } N W'\subseteq\{0,1\}^N W ′ ⊆ { 0 , 1 } N of a nondeterministic circuit of size n O ( 1 ) n^{O(1)} n O ( 1 ) . Some a ∈ W ′ a\in W' a ∈ W ′ has a polynomial-time description of length N − log ∣ W ∣ + O ( log n ) N-\log|W|+O(\log n) N − log ∣ W ∣ + O ( log n ) . The reconstruction algorithm depends only on a polynomial bound on the circuit size. To see this, fix b = ⌈ N − log ∣ W ∣ ⌉ b=\lceil N-\log|W|\rceil b = ⌈ N − log ∣ W ∣ ⌉ . A uniform affine map F : { 0 , 1 } N → { 0 , 1 } N F:\{0,1\}^N\to\{0,1\}^N F : { 0 , 1 } N → { 0 , 1 } N takes the 2 b 2^b 2 b zero-padded b b b -bit strings pairwise independently to uniform outputs. The hit count on W W W has mean at least one and variance at most its mean, so the probability of a hit is at least 1 / 2 1/2 1/2 . Whether some index is mapped into W ′ W' W ′ is an NP test of the map, implementable by a polynomial-size circuit with one SAT gate. The Klivans–van Melkebeek generator under H H H with logarithmic seed fools this test to error 1 / 4 1/4 1/4 [15 , 23 ] . Encode the seed, index length, and hit index. Decoding evaluates the generator and affine map in polynomial time.
Proof of Theorem 5.1. An empty side needs a flag. For K < n K<n K < n , greedy halving gives a cover with r ≤ ⌈ log K ⌉ + 1 r\le\lceil\log K\rceil+1 r ≤ ⌈ log K ⌉ + 1 anchors. Listing it costs r n = r ( n − r ) + O ( n ) rn=r(n-r)+O(n) r n = r ( n − r ) + O ( n ) since r 2 = O ( log 2 n ) = O ( n ) r^2=O(\log^2 n)=O(n) r 2 = O ( log 2 n ) = O ( n ) . For bounded n n n we may likewise use a greedy cover by adjusting the constant in the advice bound. Assume K ≥ n K\ge n K ≥ n and n ≥ 2048 n\ge2048 n ≥ 2048 . Apply Lemma 2.2 with ϵ = 1 / ( 32 n ) \epsilon=1/(32n) ϵ = 1/ ( 32 n ) and ζ = 2 / 3 \zeta=2/3 ζ = 2/3 . As in Theorem 2.3, r = ∣ J ∣ ≤ m + 1 r=|J|\le m+1 r = ∣ J ∣ ≤ m + 1 , and A = ∑ x ν ( x ) 1 + 1 / J A=\sum_x \nu(x)^{1+1/J} A = ∑ x ν ( x ) 1 + 1/ J satisfies − J log A ≥ J − O ( 1 ) -J\log A\ge J-O(1) − J log A ≥ J − O ( 1 ) .
Finite weights. Let σ = ( ϵ / 4 ) 3 / 2 \sigma=(\epsilon/4)^{3/2} σ = ( ϵ /4 ) 3/2 , τ = σ / ( 64 r ) \tau=\sigma/(64r) τ = σ / ( 64 r ) and M = n / τ 2 M=n/\tau^2 M = n / τ 2 . These choices make M M M , M τ M\tau M τ and M σ M\sigma M σ integers. Hoeffding’s bound and a union bound give M M M anchors sampled from ν \nu ν whose empirical miss frequencies s ^ ( x ) \hat{s}(x) s ^ ( x ) approximate s ( x ) s(x) s ( x ) within τ \tau τ simultaneously for x ∈ S x\in S x ∈ S . Set
t ( x ) = max { σ , s ^ ( x ) + τ } , p ^ ( x ) = ( 1 − ϵ ) s ^ ( x ) J / ζ + ϵ / K , h ( x ) = max { 0 , ⌊ log ( 1 / p ^ ( x ) ) ⌋ } . t(x)=\max\{\sigma,\hat{s}(x)+\tau\},\qquad\hat{p}(x)=(1-\epsilon)\hat{s}(x)^J/\zeta+\epsilon/K,\qquad h(x)=\max\{0,\lfloor\log(1/\hat{p}(x))\rfloor\}. t ( x ) = max { σ , s ^ ( x ) + τ } , p ^ ( x ) = ( 1 − ϵ ) s ^ ( x ) J / ζ + ϵ / K , h ( x ) = max { 0 , ⌊ log ( 1/ p ^ ( x ))⌋} .
Write R = ⌊ log ( K / ϵ ) ⌋ R=\lfloor\log(K/\epsilon)\rfloor R = ⌊ log ( K / ϵ )⌋ , so 0 ≤ h ≤ R 0\le h\le R 0 ≤ h ≤ R . The sampled names and the tables for the integer values M t ( x ) Mt(x) M t ( x ) and h ( x ) h(x) h ( x ) can be hardwired into polynomial-size circuits. There are only M + 1 M+1 M + 1 possible frequencies. These tables specify integer outputs even when J J J is irrational. The following estimates hold:
s ( x ) ≤ t ( x ) , ∑ x ∈ S t ( x ) r ≤ 0.70 , ν ( x ) ≤ 2 1 − h ( x ) , h ( x ) ≥ log ( 1 / ν ( x ) ) − 2. s(x)\le t(x),\qquad\sum_{x\in S}t(x)^r\le0.70,\qquad\nu(x)\le2^{1-h(x)},\qquad h(x)\ge\log(1/\nu(x))-2. s ( x ) ≤ t ( x ) , x ∈ S ∑ t ( x ) r ≤ 0.70 , ν ( x ) ≤ 2 1 − h ( x ) , h ( x ) ≥ log ( 1/ ν ( x )) − 2.
Indeed, where s ( x ) ≥ σ s(x)\ge\sigma s ( x ) ≥ σ the relative error in s ^ ( x ) \hat{s}(x) s ^ ( x ) is at most 1 / ( 64 r ) 1/(64r) 1/ ( 64 r ) and t ( x ) / s ( x ) ≤ 1 + 1 / ( 32 r ) t(x)/s(x)\le1+1/(32r) t ( x ) / s ( x ) ≤ 1 + 1/ ( 32 r ) . The corresponding terms in the power sum are at most e 1 / 32 s ( x ) J e^{1/32}s(x)^J e 1/32 s ( x ) J , and the estimated and true values of ν ( x ) \nu(x) ν ( x ) differ by at most a factor two. For s ( x ) < σ s(x)<\sigma s ( x ) < σ use t ( x ) ≤ 2 σ t(x)\le2\sigma t ( x ) ≤ 2 σ and ( 2 σ ) J = ( ϵ / 4 ) 3 J ≤ ( 4 ζ / K ) 3 (2\sigma)^J=(\epsilon/4)^{3J}\le(4\zeta/K)^3 ( 2 σ ) J = ( ϵ /4 ) 3 J ≤ ( 4 ζ / K ) 3 . The resulting full sum is at most e 1 / 32 ζ + K ( 4 ζ / K ) 3 < 0.70 e^{1/32}\zeta+K(4\zeta/K)^3<0.70 e 1/32 ζ + K ( 4 ζ / K ) 3 < 0.70 for large n n n . The small terms’ individual nonuniform mass before smoothing is at most ϵ / K \epsilon/K ϵ / K , both in the empirical and the true law, since ( 4 ζ / K ) 3 / ζ ≤ ϵ / K (4\zeta/K)^3/\zeta\le\epsilon/K ( 4 ζ / K ) 3 / ζ ≤ ϵ / K for K ≥ n ≥ 2048 K\ge n\ge2048 K ≥ n ≥ 2048 . The factor-two comparison then gives h ( x ) ≥ log ( 1 / ν ( x ) ) − 2 h(x)\ge\log(1/\nu(x))-2 h ( x ) ≥ log ( 1/ ν ( x )) − 2 and ν ( x ) ≤ 2 1 − h ( x ) \nu(x)\le2^{1-h(x)} ν ( x ) ≤ 2 1 − h ( x ) .
Paying for the anchor descriptions. For ρ = E ν 2 − h ( a ) / J \rho=\mathbb{E}_{\nu}2^{-h(a)/J} ρ = E ν 2 − h ( a ) / J , rounding the weights costs at most two bits per anchor in the power-moment estimate.
ρ ≤ 2 2 / J A , − J log ρ ≥ J − O ( 1 ) . \rho\le2^{2/J}A,\qquad-J\log\rho\ge J-O(1). ρ ≤ 2 2/ J A , − J log ρ ≥ J − O ( 1 ) .
Anchor blocks. Describing the anchors separately would spend O ( log n ) O(\log n) O ( log n ) bits per anchor on seeds and length fields. We describe whole blocks. A block of k k k anchors can cost a factor ( min x t ( x ) ) − k (\min_x t(x))^{-k} ( min x t ( x ) ) − k in the accuracy of the counting test. The following choice keeps that factor polynomial and the total description overhead linear. Set
j = min { ⌊ n + 6 r ⌋ , ⌈ log ( 1 / σ ) ⌉ } , w ( x ) = max { t ( x ) , 2 − j } , b = max { 1 , ⌊ log n j ⌋ } . j=\min\left\{\left\lfloor\frac{n+6}{r}\right\rfloor,\left\lceil\log(1/\sigma)\right\rceil\right\},\qquad w(x)=\max\{t(x),2^{-j}\},\qquad b=\max\left\{1,\left\lfloor\frac{\log n}{j}\right\rfloor\right\}. j = min { ⌊ r n + 6 ⌋ , ⌈ log ( 1/ σ ) ⌉ } , w ( x ) = max { t ( x ) , 2 − j } , b = max { 1 , ⌊ j log n ⌋ } .
If the second term attains the minimum defining j j j , then w = t w=t w = t . Otherwise K 2 − j r ≤ 1 / 64 K2^{-jr}\le1/64 K 2 − j r ≤ 1/64 . Hence ∑ x w ( x ) r ≤ 0.70 + 1 / 64 \sum_xw(x)^r\le0.70+1/64 ∑ x w ( x ) r ≤ 0.70 + 1/64 . Partition the r r r positions into B = ⌈ r / b ⌉ B=\lceil r/b\rceil B = ⌈ r / b ⌉ consecutive blocks, the last possibly shorter. For every block length k k k ,
2 j k = n O ( 1 ) , B log n = O ( n ) . 2^{jk}=n^{O(1)},\qquad B\log n=O(n). 2 j k = n O ( 1 ) , B log n = O ( n ) .
Indeed, j k ≤ max { j , log n } = O ( log n ) jk\le\max\{j,\log n\}=O(\log n) j k ≤ max { j , log n } = O ( log n ) , and 1 / b ≤ 2 j / log n 1/b\le2j/\log n 1/ b ≤ 2 j / log n while r j ≤ n + 6 + r rj\le n+6+r r j ≤ n + 6 + r . Put D = M 2 j D=M2^j D = M 2 j . All D w ( x ) Dw(x) D w ( x ) are integers and D = n O ( 1 ) D=n^{O(1)} D = n O ( 1 ) .
Let S i S_i S i consist of the vertices of S S S still uncovered after i i i chosen anchors. At the block boundaries use the potential
Φ i = ∑ x ∈ S i w ( x ) r − i , Ξ i = 1 16 2 − ∑ u ≤ i h ( a u ) / J ρ − i , P i = Φ i + Ξ i . \Phi_i=\sum_{x\in S_i}w(x)^{r-i},\qquad\Xi_i=\frac{1}{16}2^{-\sum_{u\le i}h(a_u)/J}\rho^{-i},\qquad P_i=\Phi_i+\Xi_i. Φ i = x ∈ S i ∑ w ( x ) r − i , Ξ i = 16 1 2 − ∑ u ≤ i h ( a u ) / J ρ − i , P i = Φ i + Ξ i .
Initially P 0 ≤ 0.70 + 1 / 64 + 1 / 16 P_0\le0.70+1/64+1/16 P 0 ≤ 0.70 + 1/64 + 1/16 . Choose a provisional block a = ( a i + 1 , … , a i + k ) a=(a_{i+1},\ldots,a_{i+k}) a = ( a i + 1 , … , a i + k ) from ν ⊗ k \nu^{\otimes k} ν ⊗ k . A surviving vertex x x x remains uncovered with probability s ( x ) k s(x)^k s ( x ) k , so s ( x ) ≤ w ( x ) s(x)\le w(x) s ( x ) ≤ w ( x ) gives E Φ i + k ≤ Φ i \mathbb{E}\Phi_{i+k}\le\Phi_i E Φ i + k ≤ Φ i . Independence gives E Ξ i + k = Ξ i \mathbb{E}\Xi_{i+k}=\Xi_i E Ξ i + k = Ξ i . With δ = 1 / ( 16 r ) \delta=1/(16r) δ = 1/ ( 16 r ) , Markov’s inequality therefore assigns mass at least δ / ( 1 + δ ) \delta/(1+\delta) δ / ( 1 + δ ) to blocks with P i + k ≤ ( 1 + δ ) P i P_{i+k} \le(1+\delta)P_i P i + k ≤ ( 1 + δ ) P i . Bin these blocks by H = ∑ u = i + 1 i + k h ( a u ) H = \sum_{u=i+1}^{i+k} h(a_u) H = ∑ u = i + 1 i + k h ( a u ) . There are at most k R + 1 kR+1 k R + 1 bins, and each tuple in bin H H H has mass at most 2 k − H 2^{k-H} 2 k − H . Some bin thus contains a set V V V of such blocks of cardinality
∣ V ∣ ≥ 2 H − k δ ( 1 + δ ) ( k R + 1 ) . |V| \ge2^{H-k}\frac{\delta}{(1+\delta)(kR+1)}. ∣ V ∣ ≥ 2 H − k ( 1 + δ ) ( k R + 1 ) δ .
Certifying a block. Fix this bin, put e = r − i − k e=r-i-k e = r − i − k , Φ i ′ = ∑ x ∈ S i w ( x ) e \Phi'_i=\sum_{x\in S_i}w(x)^e Φ i ′ = ∑ x ∈ S i w ( x ) e , and write ξ \xi ξ for the common value of Ξ i + k \Xi_{i+k} Ξ i + k in the bin. If W ( a ) W(\mathbf{a}) W ( a ) is the sum of w ( x ) e w(x)^e w ( x ) e over the vertices of S i S_i S i certified by at least one entry of a \mathbf{a} a , then
P i + k = Φ i ′ + ξ − W ( a ) , T 0 = Φ i ′ + ξ − ( 1 + δ ) P i . P_{i+k}=\Phi'_i+\xi-W(\mathbf{a}), \qquad T_0=\Phi'_i+\xi-(1+\delta)P_i. P i + k = Φ i ′ + ξ − W ( a ) , T 0 = Φ i ′ + ξ − ( 1 + δ ) P i .
Every block in V V V has W ( a ) ≥ T 0 W(\mathbf{a})\ge T_0 W ( a ) ≥ T 0 . In particular ξ ≤ ( 1 + δ ) P i \xi\le(1+\delta)P_i ξ ≤ ( 1 + δ ) P i , so T 0 ≤ Φ i ′ ≤ 2 j k P i T_0\le\Phi'_i\le2^{jk}P_i T 0 ≤ Φ i ′ ≤ 2 j k P i .
The integer D e W ( a ) D^eW(\mathbf{a}) D e W ( a ) counts pairs ( x , z ) (x,z) ( x , z ) for which x ∈ S i x\in S_i x ∈ S i , some block entry certifies x x x , and 1 ≤ z ≤ ( D w ( x ) ) e 1\le z\le(Dw(x))^e 1 ≤ z ≤ ( D w ( x ) ) e . This is a nondeterministically recognizable set. Membership in S S S uses the path to the fixed king, and the earlier anchors determine S i S_i S i . The binary representation of z z z uses O ( n log n ) O(n\log n) O ( n log n ) bits. Check that each block entry is in S S S and that the entries have total bin value H H H . When T 0 > 0 T_0>0 T 0 > 0 , apply the set lower-bound test at integer threshold ⌈ D e T 0 ⌉ \lceil D^eT_0\rceil ⌈ D e T 0 ⌉ with relative slack η = δ 2 − j k \eta=\delta2^{-jk} η = δ 2 − j k . Its inverse is polynomial in n n n . All of V V V pass. Any passing block has
W ( a ) ≥ ( 1 − η ) T 0 ≥ T 0 − δ P i , P i + k ≤ ( 1 + 2 δ ) P i . W(\mathbf{a})\ge(1-\eta)T_0\ge T_0-\delta P_i,\qquad P_{i+k}\le(1+2\delta)P_i. W ( a ) ≥ ( 1 − η ) T 0 ≥ T 0 − δ P i , P i + k ≤ ( 1 + 2 δ ) P i .
When T 0 ≤ 0 T_0\le0 T 0 ≤ 0 , the membership and bin tests alone suffice. The earlier anchors, empirical tables, king and integer threshold occur only in this nonuniform test. Inductively P i < 1 P_i<1 P i < 1 , so the bound on T 0 T_0 T 0 gives a threshold of O ( n log n ) O(n\log n) O ( n log n ) bits.
Apply the second short-description tool with N = k n N=kn N = k n . Some passing block has description length k n − log ∣ V ∣ + O L ( log n ) ≤ k n − H + k + O L ( log n ) kn-\log|V|+O_L(\log n)\le kn-H+k+O_L(\log n) k n − log ∣ V ∣ + O L ( log n ) ≤ k n − H + k + O L ( log n ) . Choosing such a block at every step keeps P i ≤ ( 1 + 2 δ ) B P 0 ≤ e 1 / 8 ( 0.70 + 1 / 64 + 1 / 16 ) < 1 P_i\le(1+2\delta)^B P_0\le e^{1/8}(0.70+1/64+1/16)<1 P i ≤ ( 1 + 2 δ ) B P 0 ≤ e 1/8 ( 0.70 + 1/64 + 1/16 ) < 1 at each boundary. At the last boundary Φ r = ∣ S r ∣ \Phi_r=|S_r| Φ r = ∣ S r ∣ is an integer and hence zero. Also Ξ r < 1 \Xi_r<1 Ξ r < 1 gives
∑ u = 1 r h ( a u ) > − J r log ρ − 4 J ≥ r 2 − O ( r ) . \sum_{u=1}^{r}h(a_u)>-Jr\log\rho-4J\ge r^2-O(r). u = 1 ∑ r h ( a u ) > − J r log ρ − 4 J ≥ r 2 − O ( r ) .
The decoder reconstructs all r r r names from the block descriptions, compares the input with them in the indicated orientation, and complements the outcome for a negative side. Framing the descriptions takes at most O ( log n ) O(\log n) O ( log n ) bits per block. Summing over the blocks gives
r n − ∑ u = 1 r h ( a u ) + O L ( r + B log n ) ≤ r ( n − r ) + O L ( n ) . rn-\sum_{u=1}^{r}h(a_u)+O_L(r+B\log n)\le r(n-r)+O_L(n). r n − u = 1 ∑ r h ( a u ) + O L ( r + B log n ) ≤ r ( n − r ) + O L ( n ) .
The reconstruction uses polynomial time and at most r ≤ m + 1 r\le m+1 r ≤ m + 1 nonadaptive selector comparisons.
The algebraic lower bound
Write K = 2 m K=2^m K = 2 m , a = n − m a=n-m a = n − m , and T = 2 a T=2^a T = 2 a . Partition the n n n -bit vertices into K K K buckets of size T T T . In each bucket β \beta β choose a uniform core t β t_\beta t β and a fair label λ β \lambda_\beta λ β , independently. The members are exactly the cores of label one. Cores beat noncores, positive cores beat negative cores, and equal-label cores use one independent fair coin per unordered pair. Order noncores lexicographically and set the diagonal to zero. This is the Boolean hidden-core distribution of [5 ] . Conditional on the table E E E , sample one uniform extension from its polynomial fiber in each available finite field, independently across fields. Degrees are bounded in each variable by a prescribed integer at least two. All executions see the same sampled tuple z z z . We first fix a deterministic interpreter D D D making at most q q q queries on every history. Its description, tape when present, and advice word are fixed independently of the draw. The next subsection defines visibility and the addressed set Adr \operatorname{Adr} Adr and proves their locality properties.
Which entries a degree-two query can reveal
Fix a table E E E and, independently in each field, sample its extension uniformly from the finite affine space of polynomials with individual degree at most d d d agreeing with E E E on the cube. Here d ≥ 2 d \ge2 d ≥ 2 ; it may depend on the field. Fix the tape and advice of a classical interpreter for the following two lemmas. A recorded transcript includes the queries and their answers. For a set S S S of queried points in one field, call a Boolean position ( u , v ) (u,v) ( u , v ) visible if no polynomial in the permitted degree class vanishes on S S S and restricts on the cube to the point indicator δ ( u , v ) \delta_{(u,v)} δ ( u , v ) . Write B ( S ) B(S) B ( S ) for these positions.
Lemma 6.1 (Transcript privacy). The likelihood of a recorded transcript depends on the underlying table only through the visible positions of its query set in each field.
Proof. For each invisible position choose a polynomial witnessing invisibility. If two tables agree on B ( S ) B(S) B ( S ) , the sum of these polynomials weighted by their entrywise differences translates one extension fiber onto the other while preserving its evaluations on S S S . Uniform fiber measures therefore give the same probability to every evaluation cylinder. For a recorded adaptive transcript earlier answers determine later queries. Its cylinder imposes just the recorded evaluation constraints, which factor over fields conditional on the table.
For points P P P in one copy of field n n n -space, let V ( P ) V(P) V ( P ) be the Boolean vertices whose evaluation functionals on multilinear polynomials lie in the span of the evaluations at P P P . Boolean evaluations form a dual basis, so ∣ V ( P ) ∣ ≤ ∣ P ∣ |V(P)| \le|P| ∣ V ( P ) ∣ ≤ ∣ P ∣ . Use superscripts ( 1 ) , ( 2 ) (1),(2) ( 1 ) , ( 2 ) for projections onto the two copies of n n n -space.
Lemma 6.2 (Product criterion). For any S = S 1 ∪ S 2 S = S_1 \cup S_2 S = S 1 ∪ S 2 and ( u , v ) ∈ B ( S ) (u,v) \in B(S) ( u , v ) ∈ B ( S ) , one has u ∈ V ( S 1 ( 1 ) ) u \in V(S_1^{(1)}) u ∈ V ( S 1 ( 1 ) ) or v ∈ V ( S 2 ( 2 ) ) v \in V(S_2^{(2)}) v ∈ V ( S 2 ( 2 ) ) .
Proof. If both alternatives fail, there are multilinear g , g ′ g,g' g , g ′ vanishing on S 1 ( 1 ) , S 2 ( 2 ) S_1^{(1)},S_2^{(2)} S 1 ( 1 ) , S 2 ( 2 ) , respectively, with g ( u ) = g ′ ( v ) = 1 g(u)=g'(v)=1 g ( u ) = g ′ ( v ) = 1 . The polynomial δ u ( Y ) g ( Y ) δ v ( Z ) g ′ ( Z ) \delta_u(Y)g(Y)\delta_v(Z)g'(Z) δ u ( Y ) g ( Y ) δ v ( Z ) g ′ ( Z ) has individual degree at most two, vanishes on S S S , and restricts on the cube to δ ( u , v ) \delta_{(u,v)} δ ( u , v ) .
For a family of query sets, let Adr \operatorname{Adr} Adr be the union of V ( S ( 1 ) ) V(S^{(1)}) V ( S ( 1 ) ) and V ( S ( 2 ) ) V(S^{(2)}) V ( S ( 2 ) ) over its fields. Both endpoints of a visible position belong to Adr \operatorname{Adr} Adr , by the two covers with an empty part. This monotone set has size at most twice the number of queries.
Discovery and errors
Lemma 6.3 (Discovery on one input). Let A β A_\beta A β count other cores in Adr \operatorname{Adr} Adr of the standalone run on t β t_\beta t β . If T ≥ 4 q T \ge4q T ≥ 4 q , then Pr [ A β ≥ h ] ≤ ( 4 e q / ( h T ) ) h \Pr[A_\beta\ge h] \le(4eq/(hT))^h Pr [ A β ≥ h ] ≤ ( 4 e q / ( h T ) ) h for every integer h ≥ 1 h \ge1 h ≥ 1 .
Proof. Reveal the current core and label. Before answering each query, test each newly addressed vertex in a fixed order, revealing its core status and the labels and pair coins needed among revealed cores. Lemma 6.1 permits sampling the next answer using only the exposed table entries and fresh coins, by the ratio of successive cylinder probabilities. Thus each undiscovered core remains uniform among the untested tails of its bucket. Each of the at most 2 q 2q 2 q tests discovers an additional core with conditional probability at most 1 / ( T − 2 q ) ≤ 2 / T 1/(T-2q) \le2/T 1/ ( T − 2 q ) ≤ 2/ T . Summing over the positions of h h h successful tests gives ( 2 q h ) ( 2 / T ) h \binom{2q}{h}(2/T)^h ( h 2 q ) ( 2/ T ) h .
Lemma 6.4 (Error count). Let Z Z Z count the core inputs on which D D D errs. For m ≥ 3 m \ge3 m ≥ 3 , T ≥ 32 e q T \ge32eq T ≥ 32 e q , and h ≥ 1 h \ge1 h ≥ 1 , put p = 2 − h − 1 p = 2^{-h-1} p = 2 − h − 1 . Then
Pr [ Z ≤ p K / 4 ] ≤ ( 32 e q 3 T ) K / 4 + 8 ( 8 e q h T ) h + exp ( − p K / 16 ) . \Pr[Z \le pK/4] \le\left(\frac{32eq}{3T}\right)^{K/4} + 8\left(\frac{8eq}{hT}\right)^h + \exp(-pK/16). Pr [ Z ≤ p K /4 ] ≤ ( 3 T 32 e q ) K /4 + 8 ( h T 8 e q ) h + exp ( − p K /16 ) .
Proof. Maintain the cumulative query sets and test every newly addressed vertex. Choose the next input core from the least bucket whose core location has not been exposed. Reveal that location, execute its ordinary run, and defer its label and incident coins to the end of the round. In each other unexposed bucket, either hitting its core or accumulating T / 4 T/4 T /4 distinct unsuccessful tests exposes its location, label, and coins with already exposed cores except the current core. Such a bucket receives no future round. Process tests before recording the current answer, including when one query causes several tests. Closing a round reveals its deferred variables for the exposed cores.
At the beginning of a round, its core t β t_\beta t β was unaddressed in the past. Its label and its coins are fresh. Indeed a fixed enriched history specifies the source exposures, and its answer likelihood depends only on the visible table values, all determined by those exposures. Within a round the same assertion about other unexposed buckets holds after conditioning on the current label and coins. If a visible position now joins t β t_\beta t β to v v v , apply Lemma 6.2 with the past and the current run as the two parts (exchange them for the reversed position). Since the past does not address t β t_\beta t β , the current run alone addresses v v v .
Fix a start-of-round history including t β t_\beta t β . Let P b P_b P b be the law of the ensuing history for current label b b b , excluding the closing revelation. Under an auxiliary law U U U , the current core loses to all positive cores and beats all negative cores. Keep all other entries fixed and draw the extension fibers conditional on the recorded past. The old cylinder has the same probability by privacy. For a completed history τ \tau τ , let d ( τ ) d(\tau) d ( τ ) count the other core vertices joined to the current core by a visible position in the cumulative query sets. On fixing the outside variables, at most d ( τ ) d(\tau) d ( τ ) equal-label coins must take prescribed values for all visible entries to agree with the auxiliary table. None was exposed during the round. Transcript privacy and integration over the outside variables therefore give P b ( τ ) ≥ 2 − d ( τ ) U ( τ ) P_b(\tau) \ge2^{-d(\tau)}U(\tau) P b ( τ ) ≥ 2 − d ( τ ) U ( τ ) . Whichever output D D D gives, its conditional error probability is at least 2 − h U ( d < h ) 2^{-h}U(d<h) 2 − h U ( d < h ) , including the prior 1 / 2 1/2 1/2 on the opposite label.
Stop just after the tests of the first issued query for which d ≥ h d \ge h d ≥ h , before its answer. Only the previous answered queries constrain coins of the current core. Their incident count is at most h − 1 h-1 h − 1 , even if the last query increases d d d by several units. The disjoint stopped cylinders have P b P_b P b -probability at least 2 − ( h − 1 ) 2^{-(h-1)} 2 − ( h − 1 ) times their U U U -probability. Current-run locality implies A β ≥ h A_\beta\ge h A β ≥ h on each such true history. Thus
U ( d ≥ h ) ≤ 2 h − 1 Pr [ A β ≥ h ∣ past ] . U(d \ge h) \le2^{h-1}\Pr[A_\beta\ge h \mid\text{past}]. U ( d ≥ h ) ≤ 2 h − 1 Pr [ A β ≥ h ∣ past ] .
Call a round good when the conditional probability on the right before multiplication is at most 2 − h 2^{-h} 2 − h . It errs with conditional probability at least p p p . Give each bucket its genuine starting history if selected and a cemetery symbol otherwise. By the tower property, the probability that bucket β \beta β has a bad round is at most 2 h Pr [ A β ≥ h ] 2^{h}\Pr[A_{\beta} \ge h] 2 h Pr [ A β ≥ h ] , where A β A_{\beta} A β is defined by its standalone run even if unselected. Markov’s inequality and Lemma 6.3 bound the probability of at least K / 8 K/8 K /8 bad rounds by 8 ( 8 e q / ( h T ) ) h 8(8eq/(hT))^{h} 8 ( 8 e q / ( h T ) ) h .
There are at most 2 K q 2Kq 2 K q tests, so at most 8 K q / T < K / 8 8Kq/T < K/8 8 K q / T < K /8 buckets reach the unsuccessful-test threshold. Before then, a test naturally discovers a fresh core with conditional probability at most 4 / ( 3 T ) 4/(3T) 4/ ( 3 T ) . The probability of at least K / 4 K/4 K /4 natural discoveries is at most ( 2 K q K / 4 ) ( 4 / ( 3 T ) ) K / 4 ≤ ( 32 e q / ( 3 T ) ) K / 4 \binom{2Kq}{K/4}(4/(3T))^{K/4} \le(32eq/(3T))^{K/4} ( K /4 2 K q ) ( 4/ ( 3 T ) ) K /4 ≤ ( 32 e q / ( 3 T ) ) K /4 . Outside these two exceptional events there are at least K / 2 K/2 K /2 good rounds. Select them in chronological order, padding any missing slots by independent Bernoulli-p p p variables. Goodness is known before the output. Each selected or padded error indicator X X X has conditional expectation at least p p p at selection, so its conditional exponential moment at − ln 2 -\ln2 − ln 2 is at most 1 − p / 2 1-p/2 1 − p /2 . Iterating over K / 2 K/2 K /2 slots bounds the probability of at most p K / 4 pK/4 p K /4 selected errors by exp ( − p K / 16 ) \exp(-pK/16) exp ( − p K /16 ) . On the nonexceptional event these are actual errors.
Counting advice words
Theorem 6.5 (All-core success). Let D D D be a deterministic interpreter making at most Q Q Q queries on every history, fixed independently of the draw. Suppose m ≥ 3 m \ge3 m ≥ 3 , T = 2 n − m ≥ 32 e Q T = 2^{n-m} \ge32eQ T = 2 n − m ≥ 32 e Q and j = m − ⌈ 4 log ( n + 2 ) ⌉ ≥ 1 j = m - \lceil4\log(n + 2)\rceil\ge1 j = m − ⌈ 4 log ( n + 2 )⌉ ≥ 1 . Then
Pr [ D is correct on every core input ] ≤ ( 32 e Q 3 T ) K / 4 + 8 ( 8 e Q j T ) j + exp ( − ( n + 2 ) 4 32 ) . \Pr[D\text{ is correct on every core input}] \le\left(\frac{32eQ}{3T}\right)^{K/4} + 8\left(\frac{8eQ}{jT}\right)^{j} + \exp\left(-\frac{(n+2)^4}{32}\right). Pr [ D is correct on every core input ] ≤ ( 3 T 32 e Q ) K /4 + 8 ( j T 8 e Q ) j + exp ( − 32 ( n + 2 ) 4 ) . If Q ≤ n d Q \le n^d Q ≤ n d , the right side is at most 2 − m ( n − m ) + O d ( n log n ) 2^{-m(n-m)+O_d(n\log n)} 2 − m ( n − m ) + O d ( n l o g n ) for large n n n .
Proof. Correctness on every core input means Z = 0 ≤ p K / 4 Z = 0 \le pK/4 Z = 0 ≤ p K /4 . Apply Lemma 6.4 with h = j h = j h = j , so p = 2 − j − 1 p = 2^{-j-1} p = 2 − j − 1 . Since m − j ≥ 4 log ( n + 2 ) m-j \ge4\log(n+2) m − j ≥ 4 log ( n + 2 ) , its last term is exp ( − 2 m − j − 5 ) ≤ exp ( − ( n + 2 ) 4 / 32 ) \exp(-2^{m-j-5}) \le\exp(-(n+2)^4/32) exp ( − 2 m − j − 5 ) ≤ exp ( − ( n + 2 ) 4 /32 ) . For the estimate, the middle term is 2 3 − j ( n − m ) + j log ( 8 e Q / j ) 2^{3-j(n-m)+j\log(8eQ/j)} 2 3 − j ( n − m ) + j l o g ( 8 e Q / j ) , and j ( n − m ) ≥ m ( n − m ) − ( 4 log ( n + 2 ) + 1 ) n j(n-m) \ge m(n-m) - (4\log(n+2)+1)n j ( n − m ) ≥ m ( n − m ) − ( 4 log ( n + 2 ) + 1 ) n while j log ( 8 e Q ) = O d ( n log n ) j\log(8eQ) = O_d(n\log n) j log ( 8 e Q ) = O d ( n log n ) . The first term is at most 3 − K / 4 3^{-K/4} 3 − K /4 with K ≥ 2 j ( n + 2 ) 4 ≥ n 4 K \ge2^j(n+2)^4 \ge n^4 K ≥ 2 j ( n + 2 ) 4 ≥ n 4 . Both the first and last terms are below 2 − m ( n − m ) 2^{-m(n-m)} 2 − m ( n − m ) for large n n n .
Corollary 6.6 (Ordinary advice). Fix a randomized interpreter with a finite random tape independent of the source, making at most q = q ( n ) q=q(n) q = q ( n ) adaptive classical queries, q q q polynomial. Put Q = ( 18 ( n + 2 ) + 3 ) q Q=(18(n+2)+3)q Q = ( 18 ( n + 2 ) + 3 ) q . For large n n n and every m m m with ⌈ 4 log ( n + 2 ) ⌉ + 1 ≤ m \lceil4\log(n+2)\rceil+1 \le m ⌈ 4 log ( n + 2 )⌉ + 1 ≤ m and 2 n − m ≥ 32 e Q 2^{n-m} \ge32eQ 2 n − m ≥ 32 e Q , with probability at least 1 − 2 − n 1-2^{-n} 1 − 2 − n over the hidden cores and the extension tuple, no ordinary word of length at most m ( n − m ) − C q n log n m(n-m)-C_qn\log n m ( n − m ) − C q n log n gives pointwise error 1 / 3 1/3 1/3 . In particular, at m = ⌊ n / 2 ⌋ m=\lfloor n/2\rfloor m = ⌊ n /2 ⌋ ordinary advice at pointwise error 1 / 3 1/3 1/3 requires n 2 / 4 − O q ( n log n ) n^2/4-O_q(n\log n) n 2 /4 − O q ( n log n ) bits.
Proof. Repeat the machine independently with the same word an odd number of times between 18 ( n + 2 ) 18(n+2) 18 ( n + 2 ) and 18 ( n + 2 ) + 2 18(n+2)+2 18 ( n + 2 ) + 2 and take the majority. Pointwise error 1 / 3 1/3 1/3 drops below 2 − n − 2 2^{-n-2} 2 − n − 2 , so all K ≤ 2 n K \le2^n K ≤ 2 n core inputs are answered correctly on at least three quarters of the combined tapes. For a fixed word w w w and combined tape R R R , the amplified interpreter is a deterministic D w , R D_{w,R} D w , R with at most Q Q Q queries. By Markov’s inequality and Theorem 6.5, the probability over the source that w w w gives pointwise error 1 / 3 1/3 1/3 is at most 4 3 E R Pr [ D w , R correct on every core ] ≤ 4 3 2 − m ( n − m ) + O q ( n log n ) \frac{4}{3}\mathbb{E}_R\Pr[D_{w,R}\text{ correct on every core}] \le\frac{4}{3}2^{-m(n-m)+O_q(n\log n)} 3 4 E R Pr [ D w , R correct on every core ] ≤ 3 4 2 − m ( n − m ) + O q ( n l o g n ) . A union bound over the fewer than 2 ℓ + 1 2^{\ell+1} 2 ℓ + 1 words of length at most ℓ = m ( n − m ) − C q n log n \ell=m(n-m)-C_qn\log n ℓ = m ( n − m ) − C q n log n finishes the proof for a suitable C q C_q C q . The words may depend on the entire realized tuple of extensions.
Lemma 6.7 (Compressed exact cover). With probability 1 − O ( m − 2 ) 1-O(m^{-2}) 1 − O ( m − 2 ) one deterministic polynomial-time decoder is exact using m a + O ( n ) ma+O(n) ma + O ( n ) ordinary bits and at most m + 2 m+2 m + 2 Boolean comparisons.
Proof. Take ⌈ log m ⌉ \lceil\log m\rceil ⌈ log m ⌉ disjoint public groups of 4 m 4m 4 m buckets. Each contains at least m + 2 m+2 m + 2 positives except with probability exp ( − Ω ( m ) ) \exp(-\Omega(m)) exp ( − Ω ( m )) . In each group choose its first m + 2 m+2 m + 2 positive cores. Conditional on labels and locations, the probability that all positives outside the groups are certified by a given candidate is at least 1 − 2 m 2 − m − 2 = 3 / 4 1-2^{m}2^{-m-2}=3/4 1 − 2 m 2 − m − 2 = 3/4 , independently for the different candidates. The probability all candidates fail externally is at most m − 2 m^{-2} m − 2 . A union bound over candidates and positive vertices inside the groups bounds the chance that any such vertex misses a candidate by 4 m ⌈ log m ⌉ 2 2 − m − 2 4m\lceil\log m\rceil2^{2-m-2} 4 m ⌈ log m ⌉ 2 2 − m − 2 . Store a successful group’s index, its 4 m 4m 4 m -bit selection mask, and the m + 2 m+2 m + 2 tails. The decoder reconstructs its positive anchors in bucket order.
The multilinear threshold
A Boolean comparison reads one entry of a row of the table. In the multilinear extension, evaluating at the midpoint of that row gives its sum. The only advice needed to interpret this sum is the size of the cut.
Theorem 7.1 (The exact ordinary advice cost at degree one). Let N = 2 n N=2^n N = 2 n , n ≥ 1 n\ge1 n ≥ 1 . Given the canonical multilinear extensions of a selector table over the finite fields, a uniform deterministic polynomial-time decoder recognizes every legal cut using n + 1 n+1 n + 1 fixed-width advice bits and O ( n / log ( n + 1 ) ) O(n/\log(n+1)) O ( n / log ( n + 1 )) nonadaptive queries over prime fields of order at most 4 n 4n 4 n . With a public prime p > N p>N p > N , one query over F p \mathbb{F}_p F p suffices, in time polynomial in n + log p n+\log p n + log p .
The fixed width n + 1 n+1 n + 1 is optimal even with the entire table available and pointwise error strictly below 1 / 2 1/2 1/2 . If the length of a variable-length word is supplied for free, the exact worst-case ordinary advice cost is n n n .
Proof. Write k = ∣ P ∣ k=|P| k = ∣ P ∣ . A member beats all N − k N-k N − k nonmembers. A nonmember can beat only the other nonmembers, of which there are at most N − k − 1 N-k-1 N − k − 1 . Consequently x ∈ P x\in P x ∈ P exactly when deg + ( x ) ≥ N − k \deg^{+}(x)\ge N-k deg + ( x ) ≥ N − k .
For odd p p p , put z ∗ = ( 2 − 1 , … , 2 − 1 ) ∈ F p n z_*=(2^{-1},\ldots,2^{-1})\in\mathbb{F}_p^n z ∗ = ( 2 − 1 , … , 2 − 1 ) ∈ F p n . Every Boolean Lagrange basis polynomial in the second argument has value 2 − n 2^{-n} 2 − n at z ∗ z_* z ∗ . The canonical multilinear extension therefore obeys
N E m l ( x , z ∗ ) = deg + ( x ) ( m o d p ) . (1) NE_{\mathrm{ml}}(x,z_*)=\deg^{+}(x)\pmod p. \tag*{(1)} N E ml ( x , z ∗ ) = deg + ( x ) ( mod p ) . (1)
The residue determines the degree when p > N p>N p > N . For the uniform small-field version, sieve all primes in ( 2 n , 4 n ] (2n,4n] ( 2 n , 4 n ] . Their product exceeds N N N . Indeed, for 2 n ≥ 21 2n\ge21 2 n ≥ 21 , the interval contains more than 3 ( 2 n ) / ( 5 ln ( 2 n ) ) 3(2n)/(5\ln(2n)) 3 ( 2 n ) / ( 5 ln ( 2 n )) and fewer than 7 ( 2 n ) / ( 5 ln ( 2 n ) ) 7(2n)/(5\ln(2n)) 7 ( 2 n ) / ( 5 ln ( 2 n )) primes by Rosser and Schoenfeld [20 Corollary 3] . Thus the natural logarithm of their product exceeds 6 n / 5 > n ln 2 6n/5>n\ln2 6 n /5 > n ln 2 . For 1 ≤ n ≤ 10 1\le n\le10 1 ≤ n ≤ 10 the product inequality follows by direct multiplication. The Chinese remainder theorem recovers the integer degree in [ 0 , N − 1 ] [0,N-1] [ 0 , N − 1 ] from the queried residues in polynomial time. A fixed-width word encodes k ∈ { 0 , … , N } k\in\{0,\ldots,N\} k ∈ { 0 , … , N } in n + 1 n+1 n + 1 bits. With variable lengths, encode k < N k<N k < N in n n n bits and k = N k=N k = N by the empty word.
For optimality fix one transitive tournament on N N N ordered vertices. Its N + 1 N+1 N + 1 initial segments are all legal cuts and have identical oracle tables and identical canonical extensions. Two different cuts disagree on some input. On that input a decoder using the same advice has the same output distribution for both, so its error is at least 1 / 2 1/2 1/2 on one of them. Thus N + 1 N+1 N + 1 distinct words are necessary. There are 2 ℓ 2^\ell 2 ℓ words of fixed width ℓ \ell ℓ and 2 ℓ + 1 − 1 2^{\ell+1}-1 2 ℓ + 1 − 1 of length at most ℓ \ell ℓ , giving the two exact values.
The size of the components adjacent to a cut
The strong components of a tournament are linearly ordered, with all edges pointing from earlier to later components. For a nontrivial legal cut ( E , P ) (E,P) ( E , P ) , let B + B^+ B + be the last positive component and B − B^- B − the first negative component. Put B = min { ∣ B + ∣ , ∣ B − ∣ } B=\min\{|B^+|,|B^-|\} B = min { ∣ B + ∣ , ∣ B − ∣ } , v = log 2 B v=\log_2 B v = log 2 B , and u = min { v , n / 2 } u=\min\{v,n/2\} u = min { v , n /2 } .
Theorem 8.1 (Advice at a prescribed boundary-component size). There is a computable decoder using u ( n − u ) + O ( n ) u(n-u)+O(n) u ( n − u ) + O ( n ) ordinary advice bits and ⌈ v ⌉ + 1 \lceil v\rceil+1 ⌈ v ⌉ + 1 nonadaptive Boolean comparisons with zero error. Conversely, fix any randomized decoder making polynomially many adaptive classical algebraic queries with ordinary advice. For each sufficiently large n n n and each integer 3 ≤ B ≤ 2 n − 1 3\leq B\leq2^{n-1} 3 ≤ B ≤ 2 n − 1 , there is a legal cut with exactly this boundary-component size and a fixed tuple of individual-degree-two extensions requiring at least u ( n − u ) − O M ( n log n ) u(n-u)-O_M(n\log n) u ( n − u ) − O M ( n log n ) bits for pointwise error at most 1 / 3 1/3 1/3 . The same additive estimate holds trivially for B = 1 B=1 B = 1 ; a tournament component of size two does not occur. For a P P P -selective language a deterministic polynomial-time decoder uses n ( ⌊ v ⌋ + 1 ) + O ( 1 ) n(\lfloor v\rfloor+1)+O(1) n (⌊ v ⌋ + 1 ) + O ( 1 ) ordinary advice bits unconditionally. Under the SAT-gate hardness hypothesis, the polynomial-time upper bound for a P P P -selective language is u ( n − u ) + O L ( n ) u(n-u)+O_L(n) u ( n − u ) + O L ( n ) .
Proof. Orient the tournament so that the chosen boundary component C C C , of size B B B , is the last component of its side and that side beats its complement. A cover of C C C by anchors in C C C recognizes the entire side: all its earlier components beat every anchor and all vertices on the other side lose to every anchor. The ordinary cover-density bound on the tournament induced by C C C and the universal codebook construction give u ( n − u ) + O ( n ) u(n-u)+O(n) u ( n − u ) + O ( n ) bits by Theorem 2.3 . In detail, hardwire no instance data in the codebook. Group tournaments with a marked subset by ⌈ log 2 B ⌉ \lceil\log_2 B\rceil ⌈ log 2 B ⌉ , choose a codebook for each group by the finite probabilistic construction, and let the advice specify the group, entry, prefix length and orientation. There are at most 2 O ( 2 2 n ) 2^{O(2^{2n})} 2 O ( 2 2 n ) marked tournaments, which adds O ( n ) O(n) O ( n ) index bits to minus the logarithm of the covering density.
For the unconditional polynomial-time bound run Ko’s halving inside C C C . In any nonempty R ⊆ C R\subseteq C R ⊆ C some vertex is beaten by at least ( ∣ R ∣ − 1 ) / 2 (|R|-1)/2 ( ∣ R ∣ − 1 ) /2 others of R R R ; as an anchor it certifies itself and them, so fewer than ∣ R ∣ / 2 |R|/2 ∣ R ∣/2 vertices of R R R remain. After ⌊ v ⌋ + 1 \lfloor v\rfloor+1 ⌊ v ⌋ + 1 anchors nothing remains. The advice lists these anchors in full together with the orientation and side bits, and the decoder compares its input with each anchor using the selector.
For the conditional upper bound one needs a small nondeterministic membership test for C C C in the choice proof. In the tournament induced by C C C , take a vertex a a a of maximum outdegree and a vertex b b b of maximum indegree. Every x ∈ C x\in C x ∈ C is reached from a a a in at most two steps and reaches b b b in at most two steps. Indeed, if x x x beats a a a and cannot be reached from a a a in two steps, x x x beats all outneighbors of a a a as well, contradicting maximality. The reverse assertion follows by reversing the edges. Any vertex on directed paths of the form a ⇝ x ⇝ b a\leadsto x\leadsto b a ⇝ x ⇝ b belongs to C C C , because b b b reaches a a a . Thus a circuit recognizing C C C can hardwire a , b a,b a , b and guess the two possible intermediate vertices. Replacing the side membership test in the conditional anchor-choice proof of Theorem 5.1 with this circuit gives r ( n − r ) + O L ( n ) r(n-r)+O_L(n) r ( n − r ) + O L ( n ) bits for some r ≤ ⌈ v ⌉ + 1 r\leq\lceil v\rceil+1 r ≤ ⌈ v ⌉ + 1 . The maximum of r ( n − r ) r(n-r) r ( n − r ) in this range is at most u ( n − u ) + O ( n ) u(n-u)+O(n) u ( n − u ) + O ( n ) . The circuit and its two hardwired vertices are used to prove existence of a seed and index. Their descriptions are not needed by the decoder.
For the lower bound let N = n − 1 N=n-1 N = n − 1 . Given a cut on { 0 , 1 } N \{0,1\}^N { 0 , 1 } N , put p = ∣ P ∣ p=|P| p = ∣ P ∣ and assume 3 ≤ p ≤ B − 3 3\leq p\leq B-3 3 ≤ p ≤ B − 3 . Keep the 2 N 2^N 2 N old vertices with prefix zero. Split the new-prefix vertices in lexicographic order into sets W , U , T W,U,T W , U , T of sizes p , B − p , 2 N − B p,B-p,2^N-B p , B − p , 2 N − B . The positive set is 0 P ∪ U ∪ T 0P\cup U\cup T 0 P ∪ U ∪ T and the negative set is 0 P c ∪ W 0P^c\cup W 0 P c ∪ W . Orient U U U and W W W by descending rank, reversing the extreme edge in each. Each contains a directed Hamilton cycle since its size is at least three. Give T T T any public internal orientation. Put T T T above every other vertex, U U U above all old vertices and W W W , and all old vertices above W W W . Retain the old table among old vertices. Make just two exceptions: for public representatives u 0 ∈ U u_0 \in U u 0 ∈ U , w 0 ∈ W w_0 \in W w 0 ∈ W and private representatives c ∈ B o l d + c \in B_{\mathrm{old}}^+ c ∈ B old + , d ∈ B o l d − d \in B_{\mathrm{old}}^- d ∈ B old − , orient 0 c → u 0 0c \to u_0 0 c → u 0 and w 0 → 0 d w_0 \to0d w 0 → 0 d .
The exceptions preserve legality. Each old positive reaches 0 c 0c 0 c and thus U U U , and U U U can reach every old positive through a vertex other than u 0 u_0 u 0 . Each old negative can reach W W W through a vertex other than w 0 w_0 w 0 , and w 0 w_0 w 0 reaches every old negative through 0 d 0d 0 d . Hence the two components adjacent to the padded cut are precisely U ∪ 0 P U \cup0P U ∪ 0 P and 0 P c ∪ W 0P^c \cup W 0 P c ∪ W . Their sizes are B B B and 2 N 2^N 2 N . Membership on old vertices is unchanged.
For each allowed field let G G G be the multilinear extension of the public padding table, set to zero on old–old pairs. For fixed n , B n,B n , B the data determining G G G are p , c , d p,c,d p , c , d . With an old extension F F F , simulate the new extension by
F ′ ( b , x , b ′ , y ) = ( 1 − b ) ( 1 − b ′ ) F ( x , y ) + G ( b , x , b ′ , y ) + Z ( b , x , b ′ , y ) , F'(b,x,b',y)=(1-b)(1-b')F(x,y)+G(b,x,b',y)+Z(b,x,b',y), F ′ ( b , x , b ′ , y ) = ( 1 − b ) ( 1 − b ′ ) F ( x , y ) + G ( b , x , b ′ , y ) + Z ( b , x , b ′ , y ) ,
where Z Z Z is a uniformly random individual-degree-two polynomial vanishing on the Boolean cube. Use one independent Z Z Z per field and retain these choices across the entire set of input runs. Conditional on the old source and its extensions, F ′ F' F ′ is uniform on the desired fiber by translation, independently across fields. Fixing the masks makes simulation deterministic and costs at most one old query per new query. Unrestricted local computation permits the masks in the description of the fixed-length simulator. For any all-core success bound δ \delta δ uniform over deterministic old strategies, the unconditional probability of admissible padding and all-core success for a fixed padded strategy is at most 2 3 N + 1 δ 2^{3N+1}\delta 2 3 N + 1 δ . This follows by fixing the masks, summing over all triples p , c , d p,c,d p , c , d , and then averaging over the masks.
Let Q Q Q bound the query cost after O ( n ) O(n) O ( n ) independent repetitions using the same ordinary advice. Take
m = min { ⌊ log 2 B ⌋ − 2 , ⌊ N / 2 ⌋ } , K = 2 m , T 0 = 2 N − m , j = m − ⌈ 4 log 2 ( n + 2 ) ⌉ . m=\min\{\lfloor\log_2 B\rfloor-2,\lfloor N/2\rfloor\},\qquad K=2^m,\qquad T_0=2^{N-m},\qquad j=m-\lceil4\log_2(n+2)\rceil. m = min {⌊ log 2 B ⌋ − 2 , ⌊ N /2 ⌋} , K = 2 m , T 0 = 2 N − m , j = m − ⌈ 4 log 2 ( n + 2 )⌉ .
If j < 1 j<1 j < 1 , the claimed lower bound is nonpositive for a suitable constant in the remainder. An instance with the required size exists by taking two strong components of size B B B and putting the remaining vertices above them. Otherwise take the old hidden-core source with K K K buckets of size T 0 T_0 T 0 . The fair core labels give p ≥ 3 p\geq3 p ≥ 3 with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) , and p ≤ K ≤ B / 4 p\leq K\leq B/4 p ≤ K ≤ B /4 . Since m ≤ N / 2 m\leq N/2 m ≤ N /2 and Q Q Q is polynomial, T 0 ≥ 32 e Q T_0\geq32eQ T 0 ≥ 32 e Q for large n n n . Corollary 6.4 at discovery threshold j j j gives the all-core estimate
δ ≤ ( 32 e Q 3 T 0 ) K / 4 + 8 ( 8 e Q j T 0 ) j + exp ( − 2 − j − 1 K / 16 ) ≤ 2 − m ( N − m ) + O M ( n log n ) . \delta\leq\left(\frac{32eQ}{3T_0}\right)^{K/4}+8\left(\frac{8eQ}{jT_0}\right)^j+\exp(-2^{-j-1}K/16)\leq2^{-m(N-m)+O_M(n\log n)}. δ ≤ ( 3 T 0 32 e Q ) K /4 + 8 ( j T 0 8 e Q ) j + exp ( − 2 − j − 1 K /16 ) ≤ 2 − m ( N − m ) + O M ( n l o g n ) .
Indeed m − j = O ( log n ) m-j=O(\log n) m − j = O ( log n ) , log Q = O M ( log n ) \log Q=O_M(\log n) log Q = O M ( log n ) , and K 2 − j K2^{-j} K 2 − j is at least ( n + 2 ) 4 (n+2)^4 ( n + 2 ) 4 .
If one advice word gives pointwise error 1 / 3 1/3 1/3 , its amplified decoder is correct on all K K K embedded core inputs with probability at least 3 / 4 3/4 3/4 . Average the deterministic success bound over the fixed amplification tapes and sum over the fewer than 2 ℓ + 1 2^{\ell+1} 2 ℓ + 1 words of length at most ℓ \ell ℓ . The probability of admissible padding with any such successful word is at most ( 4 / 3 ) 2 ℓ + 1 + 3 N δ (4/3)2^{\ell+1+3N}\delta ( 4/3 ) 2 ℓ + 1 + 3 N δ , even when the word is chosen after seeing the padded extensions. Taking ℓ = m ( N − m ) − C M n log n \ell=m(N-m)-C_Mn\log n ℓ = m ( N − m ) − C M n log n makes this smaller than the probability of admissible padding. This supplies the asserted cut and extension tuple. Finally ∣ m − u ∣ ≤ 3 |m-u|\leq3 ∣ m − u ∣ ≤ 3 throughout the nonvacuous range, so m ( N − m ) = u ( n − u ) + O M ( n log n ) m(N-m)=u(n-u)+O_M(n\log n) m ( N − m ) = u ( n − u ) + O M ( n log n ) .
One oracle realizing the bounds
Theorem 9.1 (Relativized sharpness). There are a Boolean oracle A A A , a degree-two extension family A ~ \widetilde{A} A , and a P A \mathrm{P}^{A} P A -selective language L L L with L ∈ P A / ( n 2 / 4 + O ( n ) ) L \in\mathrm{P}^{A}/(n^2/4+O(n)) L ∈ P A / ( n 2 /4 + O ( n )) such that the following hold for almost every independent random Boolean oracle R R R . Write O = A ⊕ R O=A\oplus R O = A ⊕ R .
H O H^{\mathrm{O}} H O holds. Every P O \mathrm{P}^{\mathrm{O}} P O -selective language L ′ L' L ′ has a deterministic polynomial-time decoder relative to O O O with n 2 / 4 + O L ′ ( n ) n^2/4+O_{L'}(n) n 2 /4 + O L ′ ( n ) ordinary advice bits.
There is a degree-two extension family O ~ \widetilde{O} O such that L ∉ B P P O ~ / ⌊ c n 2 ⌋ L\notin\mathrm{BPP}^{\widetilde{O}}/\lfloor cn^2\rfloor L ∈ / BPP O / ⌊ c n 2 ⌋ for each 0 < c < 1 / 4 0<c<1/4 0 < c < 1/4 .
In H O H^{\mathrm{O}} H O the hard function belongs to E O \mathrm{E}^{\mathrm{O}} E O and the competing circuits may use O O O and S A T O \mathrm{SAT}^{O} SAT O gates. The latter decides satisfiability of an explicitly encoded Boolean oracle circuit. Input wires and query lengths count toward circuit size.
Proof. The selector and its extensions. Use the active lengths n 0 = 4 n_0=4 n 0 = 4 , n i + 1 = 2 n i n_{i+1}=2^{n_i} n i + 1 = 2 n i . At an active length n n n , let E E E and P P P be the selected tournament and cut, put L n = P L_n=P L n = P , and use two kinds of records:
A ( 00 u v ) = E ( u , v ) ( ∣ u ∣ = ∣ v ∣ = n ) , A ( 01 x 0 2 n − n ) = 1 P ( x ) ( ∣ x ∣ = n ) . A(00uv)=E(u,v)\quad(|u|=|v|=n),\qquad A(01x0^{2^n-n})=\mathbf{1}_{P}(x)\quad(|x|=n). A ( 00 uv ) = E ( u , v ) ( ∣ u ∣ = ∣ v ∣ = n ) , A ( 01 x 0 2 n − n ) = 1 P ( x ) ( ∣ x ∣ = n ) .
Their lengths 2 n + 2 2n+2 2 n + 2 and 2 n + 2 2^n+2 2 n + 2 are disjoint throughout the tower. Unspecified records are zero and inactive language slices are empty. At an edge-record length extend over each field by
A ~ ( t , t ′ , Y , Z ) = ( 1 − t ) ( 1 − t ′ ) E ~ ( Y , Z ) . (2) \widetilde{A}(t,t',Y,Z)=(1-t)(1-t')\widetilde{E}(Y,Z). \tag*{(2)} A ( t , t ′ , Y , Z ) = ( 1 − t ) ( 1 − t ′ ) E ( Y , Z ) . (2)
Use multilinear extensions at padded membership lengths and zero at empty arities. At a skipped active length take an empty cut with a fixed legal tournament. The selector compares two strings of equal active length with one edge query. An active string is preferable to an inactive one, and either of two inactive strings can be returned. For different active lengths r < s r<s r < s we have 2 r ≤ s 2^r\le s 2 r ≤ s , so the selector can read the shorter string’s membership record and return that string precisely when it is positive. Active lengths can be recognized in polynomial time by iterating the tower up to the input length. This gives P A \mathrm{P}^{A} P A -selectivity for every choice of cuts.
One base for almost every random oracle. Predetermine a schedule of clocked randomized classical interpreters M M M with algebraic access, each repeated infinitely often. At a scheduled active length take m = ⌊ n / 2 ⌋ m=\lfloor n/2\rfloor m = ⌊ n /2 ⌋ , sample the Boolean hidden-core source, and independently conditional on its table sample an extension from each relevant degree-two fiber. One canonical encoding per field suffices. Include all fields accessible to the machine within its amplified clock, and complete the other fields multilinearly. The clock allows the O ( n ) O(n) O ( n ) repetitions used for ordinary advice. Choose the stage length large enough that the current padded membership record and all future records are out of reach. Sample the selected stages independently.
Fix any R R R and condition on all earlier choices. For the tagged union use at each arity
O ~ ( t , y ) = ( 1 − t ) A ~ ( y ) + t M L ( R ) ( y ) , \widetilde{O}(t,y)=(1-t)\widetilde{A}(y)+t\,\mathrm{ML}(R)(y), O ( t , y ) = ( 1 − t ) A ( y ) + t ML ( R ) ( y ) ,
where the last term uses the multilinear extension of the corresponding R R R -slice. This is a valid degree-two extension. For the simulation an algebraic evaluation, even at a non-Boolean tag, requires at most one current extension evaluation by (2). The remaining contributions are fixed before this stage. The finite bounds are uniform in these auxiliary functions; their evaluation requires no queries to the present hidden-core table.
Apply Corollary 6.6 to M M M at m = ⌊ n / 2 ⌋ m=\lfloor n/2\rfloor m = ⌊ n /2 ⌋ , with the auxiliary answers hardwired into the deterministic simulations, and intersect its event with Lemma 6.7. The joint failure probability is o ( 1 ) o(1) o ( 1 ) , uniformly in the fixed auxiliary answers. Advice may depend on the entire fixed oracle, as permitted there.
Choose the i i i th length in advance so that its failure probability is at most 2 − i 2^{-i} 2 − i . Borel–Cantelli gives both events on all but finitely many selected stages, almost surely for this fixed R R R . Fubini now fixes one base triple ( A , A ~ , L ~ ) (A,\widetilde{A},\widetilde{L}) ( A , A , L ) for which this holds for almost every R R R . The compressed cover gives polynomial-time recognition using m ( n − m ) + O ( n ) ≤ n 2 / 4 + O ( n ) m(n-m)+O(n)\le n^2/4+O(n) m ( n − m ) + O ( n ) ≤ n 2 /4 + O ( n ) ordinary bits at the selected lengths, with an empty-slice flag elsewhere. Finitely many exceptions can be hardwired. At the infinitely many good stages of M M M no word of length at most n 2 / 4 − C M m log n n^2/4-C_M m\log n n 2 /4 − C M m log n gives pointwise error 1 / 3 1/3 1/3 . For each 0 < c < 1 / 4 0<c<1/4 0 < c < 1/4 this length exceeds ⌊ c n 2 ⌋ \lfloor cn^2\rfloor ⌊ c n 2 ⌋ for large n n n , which proves the second assertion.
Hardness and polynomial-time reconstruction in the same world. For each fixed base A A A , every size-S S S circuit with O O O and S A T O \mathrm{SAT}^{O} SAT O gates depends only on A A A and on bits of R R R at lengths at most ( S + 2 ) b (S+2)^b ( S + 2 ) b for an absolute b b b . This follows from the explicit encoding of each queried circuit and its wires. There are at most 2 C S 2 log ( S + 2 ) 2^{CS^2\log(S+2)} 2 C S 2 l o g ( S + 2 ) such circuit descriptions, including hardwired constants. For x ∈ { 0 , 1 } n x\in\{0,1\}^n x ∈ { 0 , 1 } n put f O ( x ) = R ( 00 2 n 1 x ) f^O(x)=R(00\,2^n1x) f O ( x ) = R ( 00 2 n 1 x ) , which belongs to E O E^O E O . Take S = ⌊ 2 η n ⌋ S=\lfloor2^{\eta n}\rfloor S = ⌊ 2 η n ⌋ with 0 < η < 1 / ( 4 ( b + 1 ) ) 0<\eta<1/(4(b+1)) 0 < η < 1/ ( 4 ( b + 1 )) . Conditional on the accessible short bits, the entire truth table of f O f^O f O is uniform. The probability that any size-S S S circuit computes it is at most 2 C S 2 log ( S + 2 ) − 2 n 2^{CS^2\log(S+2)-2^n} 2 C S 2 l o g ( S + 2 ) − 2 n , summable in n n n . Thus H O H^O H O holds almost surely.
The same oracle supplies the generator in Theorem 5.1 directly. For output length N N N and fixed integer k ≥ 1 k\ge1 k ≥ 1 , take S = N k S=N^k S = N k , d = ⌈ ( 2 k + 3 ) log N ⌉ d=\lceil(2k+3)\log N\rceil d = ⌈( 2 k + 3 ) log N ⌉ and read the N N N output bits of G N , k R ( z ) G^R_{N,k}(z) G N , k R ( z ) at distinct R R R -addresses encoding ( N , k , z , j ) (N,k,z,j) ( N , k , z , j ) , z ∈ { 0 , 1 } d z\in\{0,1\}^d z ∈ { 0 , 1 } d , 1 ≤ j ≤ N 1\le j\le N 1 ≤ j ≤ N . Use a prefix 1 1 1 and a self-delimiting encoding, padding its length beyond ( S + 2 ) b (S+2)^b ( S + 2 ) b but polynomially in N N N for each k k k . Conditional on all shorter bits accessible to the circuits, the 2 d 2^d 2 d outputs are independent and uniform. Hoeffding’s inequality and the circuit count bound the probability of discrepancy exceeding 1 / 4 1/4 1/4 for any size-S S S test by 2 C S 2 log ( S + 2 ) 2 exp ( − 2 d / 8 ) 2^{CS^2\log(S+2)}2\exp(-2^d/8) 2 C S 2 l o g ( S + 2 ) 2 exp ( − 2 d /8 ) . This is summable in N N N . Intersect over the countably many k k k . The generator is computable in polynomial time with O O O . For a P O P^O P O selector the weighted counting and block-index predicates of Theorem 5.1 are nondeterministic O O O -circuit tests; their acceptance reduces to one S A T O \mathrm{SAT}^{O} SAT O gate. Applying the generator to the resulting tests gives the same n 2 / 4 + O L ′ ( n ) n^2/4+O_{L'}(n) n 2 /4 + O L ′ ( n ) advice bound. Intersect these probability-one properties of R R R with the one already obtained for the fixed base.
Equilibrium search bounds
The lower bound with adaptive payoff queries
A proposal algorithm may read q q q payoff entries, adaptively, before returning one profile. Write P ϵ [ q ] ( N ) P^{[q]}_{\epsilon}(N) P ϵ [ q ] ( N ) for its optimal worst-case success probability. No bound is imposed on computation between queries. We prove the oblivious lower bound as the case q = 0 q=0 q = 0 .
Theorem A.1. Fix 0 < ϵ < 1 / 2 0<\epsilon<1/2 0 < ϵ < 1/2 . Set n = log 2 N n=\log_2N n = log 2 N , c = 1 − H 2 ( 1 / 2 + ϵ ) c=1-H_2(1/2+\epsilon) c = 1 − H 2 ( 1/2 + ϵ ) , B = 2 q + ⌈ ( n + 2 ) 4 / ( ϵ c ) ⌉ B=2q+\lceil(n+2)^4/(\epsilon c)\rceil B = 2 q + ⌈( n + 2 ) 4 / ( ϵc )⌉ and s = max { 0 , log 2 ( N / B ) } s=\max\{0,\log_2(N/B)\} s = max { 0 , log 2 ( N / B )} . Then
− log 2 P ϵ [ q ] ( N ) ≥ s 2 4 c − O ϵ ( ( s + 1 ) log ( n + 2 ) ) . -\log_2 P^{[q]}_{\epsilon}(N)\ge\frac{s^2}{4c}-O_{\epsilon}\bigl((s+1)\log(n+2)\bigr). − log 2 P ϵ [ q ] ( N ) ≥ 4 c s 2 − O ϵ ( ( s + 1 ) log ( n + 2 ) ) .
In particular q = N o ( 1 ) q=N^{o(1)} q = N o ( 1 ) preserves the leading exponent in Theorem 3.1 . The lower bound holds for tournament games, whose off-diagonal payoffs are zero or one and whose diagonal payoffs are 1 / 2 1/2 1/2 .
We give the dependence on the accuracy as well. For 0 < ϵ ≤ ϵ 0 < 1 / 2 0<\epsilon\le\epsilon_0<1/2 0 < ϵ ≤ ϵ 0 < 1/2 , let v = log 2 ( ( n + 2 ) / c ) v=\log_2((n+2)/c) v = log 2 (( n + 2 ) / c ) . The proof gives the uniform error term O ϵ 0 ( ( s + 1 ) v / c ) O_{\epsilon_0}((s+1)v/c) O ϵ 0 (( s + 1 ) v / c ) in the displayed lower bound. In particular, an implicit constant can be taken absolute for ϵ 0 = 1 / 4 \epsilon_0=1/4 ϵ 0 = 1/4 .
Lemma A.2 (Weighted wins against one row). Let β = 1 / 2 + ϵ \beta=1/2+\epsilon β = 1/2 + ϵ , η = ϵ / ( n + 2 ) \eta=\epsilon/(n+2) η = ϵ / ( n + 2 ) and 1 < h ≤ n / c 1<h\le n/c 1 < h ≤ n / c . If w 1 , … , w h w_1,\ldots,w_h w 1 , … , w h are nonnegative and sum to one, and X 1 , … , X h X_1,\ldots,X_h X 1 , … , X h are independent fair bits, then for
all sufficiently large n n n , uniformly for 0 < ϵ ≤ ϵ 0 < 1 / 2 0 < \epsilon\le\epsilon_0 < 1/2 0 < ϵ ≤ ϵ 0 < 1/2 ,
Pr [ ∑ j w j X j > β + 2 η ] ≥ 2 − c h − O ϵ 0 ( log ( h + 2 ) ) . \Pr\left[\sum_j w_j X_j > \beta+ 2\eta\right] \ge2^{-ch-O_{\epsilon_0}(\log(h+2))}. Pr [ j ∑ w j X j > β + 2 η ] ≥ 2 − c h − O ϵ 0 ( l o g ( h + 2 )) .
Proof. Take k = ⌈ ( β + 2 η ) h ⌉ + 1 k = \lceil(\beta+ 2\eta)h\rceil+ 1 k = ⌈( β + 2 η ) h ⌉ + 1 . For h h h below a constant depending only on ϵ 0 \epsilon_0 ϵ 0 , use the event that all bits equal one. For larger h h h , k / h k/h k / h stays in a compact subinterval of ( 0 , 1 ) (0,1) ( 0 , 1 ) and k ≤ h k \le h k ≤ h . Conditional on exactly k k k wins, the weighted sum has mean k / h ≥ β + 2 η + 1 / h k/h \ge\beta+2\eta+1/h k / h ≥ β + 2 η + 1/ h and lies in [ 0 , 1 ] [0,1] [ 0 , 1 ] . It exceeds β + 2 η \beta+2\eta β + 2 η with probability at least 1 / h 1/h 1/ h . The probability of this many wins is at least 2 − h [ 1 − H 2 ( k / h ) ] / ( h + 1 ) 2^{-h[1-H_2(k/h)]}/(h+1) 2 − h [ 1 − H 2 ( k / h )] / ( h + 1 ) . Write k / h = β + δ k/h=\beta+\delta k / h = β + δ with δ = O ( η + 1 / h ) \delta=O(\eta+1/h) δ = O ( η + 1/ h ) . On the specified interval the first derivative of 1 − H 2 1-H_2 1 − H 2 at β \beta β is O ϵ 0 ( ϵ ) O_{\epsilon_0}(\epsilon) O ϵ 0 ( ϵ ) and its second derivative is bounded. Hence
h ( 1 − H 2 ( k / h ) − c ) = O ϵ 0 ( h ϵ δ + h δ 2 ) = O ϵ 0 ( 1 ) , h\left(1-H_2(k/h)-c\right)=O_{\epsilon_0}(h\epsilon\delta+h\delta^2)=O_{\epsilon_0}(1), h ( 1 − H 2 ( k / h ) − c ) = O ϵ 0 ( h ϵδ + h δ 2 ) = O ϵ 0 ( 1 ) ,
using h ≤ n / c h\le n/c h ≤ n / c and c = Θ ϵ 0 ( ϵ 2 ) c=\Theta_{\epsilon_0}(\epsilon^2) c = Θ ϵ 0 ( ϵ 2 ) . This proves the bound for arbitrary weights. □
Proof of Theorem A.1. If s < C v s<Cv s < C v the uniform bound follows from P ϵ [ q ] ( N ) ≤ 1 P_\epsilon^{[q]}(N)\le1 P ϵ [ q ] ( N ) ≤ 1 by enlarging its constant. Assume s ≥ C v s\ge Cv s ≥ C v , for a sufficiently large C C C depending only on ϵ 0 \epsilon_0 ϵ 0 . Form K = ⌊ N / B ⌋ K=\lfloor\sqrt{N/B}\rfloor K = ⌊ N / B ⌋ buckets of d = ⌊ N / K ⌋ d=\lfloor N/K\rfloor d = ⌊ N / K ⌋ actions each. From each bucket choose one action independently and uniformly. The resulting K K K core actions beat all noncore actions, including any leftover actions. Edges between core actions are independent fair coins. Fix a public order on noncore actions. Write m = log 2 K m=\log_2 K m = log 2 K . Then m = s / 2 + O ( 1 ) m=s/2+O(1) m = s /2 + O ( 1 ) , d > B d>B d > B and log 2 ( ( d − B ) / B ) = m + O ( 1 ) \log_2((d-B)/B)=m+O(1) log 2 (( d − B ) / B ) = m + O ( 1 ) .
Fix the algorithm’s coins. When it queries an edge, reveal to it the core status of both endpoints. After it outputs a pair, let z z z be the average of the two strategies, and expose for the analysis every action with z i ≥ b z_i\ge b z i ≥ b , where b = η c / ( n + 2 ) 3 b=\eta c/(n+2)^3 b = η c / ( n + 2 ) 3 . In total the set E E E of exposed names has size at most B B B . In each unresolved bucket the hidden position is uniform on its untested names, independently of the other unresolved buckets. Indeed, an inspected payoff can depend on a random edge only after both core endpoints have been identified. For h h h the number of exposed core actions, a union bound over exposure times gives, for every integer h 0 ≥ 1 h_0\ge1 h 0 ≥ 1 ,
Pr [ h ≥ h 0 ] ≤ ( B h 0 ) ( d − B ) − h 0 . \Pr[h\ge h_0]\le\binom{B}{h_0}(d-B)^{-h_0}. Pr [ h ≥ h 0 ] ≤ ( h 0 B ) ( d − B ) − h 0 .
Condition on the enlarged transcript. The total probability mass Y Y Y that z z z assigns to unexposed core actions is a sum of independent terms in [ 0 , b ] [0,b] [ 0 , b ] , with mean at most 1 / ( d − B ) 1/(d-B) 1/ ( d − B ) . The chord bound exp ( w ) ≤ 1 + ( e − 1 ) w \exp(w)\le1+(e-1)w exp ( w ) ≤ 1 + ( e − 1 ) w for 0 ≤ w ≤ 1 0\le w\le1 0 ≤ w ≤ 1 yields
Pr [ Y > η ] ≤ exp ( − η / b + e − 1 b ( d − B ) ) ≤ exp [ − Ω ( ( n + 2 ) 3 / c ) ] . \Pr[Y>\eta]\le\exp\left(-\eta/b+\frac{e-1}{b(d-B)}\right)\le\exp\left[-\Omega((n+2)^3/c)\right]. Pr [ Y > η ] ≤ exp ( − η / b + b ( d − B ) e − 1 ) ≤ exp [ − Ω (( n + 2 ) 3 / c ) ] .
Here 1 / ( d − B ) = o ( η ) 1/(d-B)=o(\eta) 1/ ( d − B ) = o ( η ) in the range under consideration since B ≥ 1 / b B\ge1/b B ≥ 1/ b and ( d − B ) / B = Θ ( K ) (d-B)/B=\Theta(K) ( d − B ) / B = Θ ( K ) .
Fix the remaining core locations. Suppose Y ≤ η Y\le\eta Y ≤ η and h < h 0 = ⌊ ( m − C ′ v ) / c ⌋ h<h_0=\lfloor(m-C'v)/c\rfloor h < h 0 = ⌊( m − C ′ v ) / c ⌋ , with C ′ C' C ′ sufficiently large and C C C chosen to make h 0 ≥ 1 h_0\ge1 h 0 ≥ 1 . No unexposed core action was queried. Its edges to the h h h exposed core actions are fresh fair bits, and the collections of these edges are independent for different challengers. If the exposed core mass a a a of z z z is positive, normalize it to a distribution on those h h h actions. By Lemma A.2 , each challenger beats more than a β + 2 η \beta+2\eta β + 2 η fraction of the normalized mass with probability at least 2 − c h − O ϵ 0 ( v ) 2^{-ch-O_{\epsilon_0}(v)} 2 − c h − O ϵ 0 ( v ) . Its payoff against z z z then exceeds
1 − a − η + a ( β + 2 η ) ≥ β 1-a-\eta+a(\beta+2\eta)\ge\beta 1 − a − η + a ( β + 2 η ) ≥ β
for large n n n . If a = 0 a=0 a = 0 , every challenger already earns at least 1 − η > β 1-\eta>\beta 1 − η > β . There are K − h ≥ K / 2 K-h\ge K/2 K − h ≥ K /2 challengers. By the choice of C ′ C' C ′ , the probability that none earns more than β \beta β is at most exp [ − Ω ( ( n + 2 ) 3 / c ) ] \exp[-\Omega((n+2)^3/c)] exp [ − Ω (( n + 2 ) 3 / c )] . Thus the success probability is at most
2 exp [ − Ω ( ( n + 2 ) 3 / c ) ] + ( B d − B ‾ ) h 0 ≤ 2 − s 2 / ( 4 c ) + O ϵ 0 ( ( s + 1 ) v / c ) . 2\exp[-\Omega((n+2)^3/c)]+\left(\frac{B}{d-\overline{B}}\right)^{h_0}\le2^{-s^2/(4c)+O_{\epsilon_0}((s+1)v/c)}. 2 exp [ − Ω (( n + 2 ) 3 / c )] + ( d − B B ) h 0 ≤ 2 − s 2 / ( 4 c ) + O ϵ 0 (( s + 1 ) v / c ) .
The same distribution of games works for every fixing of the coins. Averaging gives the theorem and the lower bound in Theorem 3.1 . □
Accuracy and advice. For q = 0 q=0 q = 0 , s = n − O ϵ 0 ( v ) s=n-O_{\epsilon_0}(v) s = n − O ϵ 0 ( v ) . Lemma 3.2 gives an upper cost n 2 / ( 4 c ) + O ( n / c + log ( n / c ) ) n^2/(4c)+O(n/c+\log(n/c)) n 2 / ( 4 c ) + O ( n / c + log ( n / c )) . To obtain a universal list for shrinking ϵ \epsilon ϵ , round payoffs using an even grid denominator D = Θ ( n / ϵ ) D=\Theta(n/\epsilon) D = Θ ( n / ϵ ) and tolerance ϵ − 1 / D \epsilon^{-1}/D ϵ − 1 / D in the sampling argument. For ϵ ≤ 1 / 4 \epsilon\le1/4 ϵ ≤ 1/4 this changes c c c by a relative O ( 1 / n ) O(1/n) O ( 1/ n ) , because c = Θ ( ϵ 2 ) c=\Theta(\epsilon^2) c = Θ ( ϵ 2 ) and c ′ ( ϵ ) = O ( ϵ ) c'(\epsilon)=O(\epsilon) c ′ ( ϵ ) = O ( ϵ ) . Consequently for log ( 1 / ϵ ) = o ( n ) \log(1/\epsilon)=o(n) log ( 1/ ϵ ) = o ( n ) both logarithmic costs equal
n 2 4 c + O ( n c log n + 2 c ) ( 0 < ϵ ≤ 1 / 4 ) . \frac{n^2}{4c}+O\left(\frac{n}{c}\log\frac{n+2}{c}\right)\qquad(0<\epsilon\le1/4). 4 c n 2 + O ( c n log c n + 2 ) ( 0 < ϵ ≤ 1/4 ) .
The same leading term for one proposal persists when log ( q + 1 ) + log ( 1 / ϵ ) = o ( n ) \log(q+1)+\log(1/\epsilon)=o(n) log ( q + 1 ) + log ( 1/ ϵ ) = o ( n ) . The lower bound further allows ordinary game-dependent advice: fix each advice word and sum the success probabilities on the common hard distribution. Constant success with ℓ \ell ℓ bits requires ℓ ≥ s 2 / ( 4 c ) − O ϵ 0 ( ( s + 1 ) v / c ) \ell\ge s^2/(4c)-O_{\epsilon_0}((s+1)v/c) ℓ ≥ s 2 / ( 4 c ) − O ϵ 0 (( s + 1 ) v / c ) . An index in the universal list gives the matching leading advice upper bound when q = N o ( 1 ) q=N^{o(1)} q = N o ( 1 ) and ϵ \epsilon ϵ is fixed.
Security strategies in general zero-sum games
Consider the same one-player task for an arbitrary N N N -by-N N N payoff matrix A ∈ [ 0 , 1 ] N × N A\in[0,1]^{N\times N} A ∈ [ 0 , 1 ] N × N of value min p max i ( A p ) i = 1 / 2 \min_p\max_i(Ap)_i=1/2 min p max i ( A p ) i = 1/2 . The column player seeks a security strategy p p p with max i ( A p ) i ≤ β = 1 / 2 + ϵ \max_i(Ap)_i\le\beta=1/2+\epsilon max i ( A p ) i ≤ β = 1/2 + ϵ . Write P ϵ s e c ( N ) P^{\mathrm{sec}}_\epsilon(N) P ϵ sec ( N ) for the optimal worst-case success probability of a game-independent proposal and L ϵ s e c ( N ) L^{\mathrm{sec}}_\epsilon(N) L ϵ sec ( N ) for the minimum size of a universal list of proposals.
Theorem A.3. For fixed 0 < ϵ < 1 / 2 0<\epsilon<1/2 0 < ϵ < 1/2 , n = log N n=\log N n = log N and c = 1 − H 2 ( β ) c=1-H_2(\beta) c = 1 − H 2 ( β ) ,
n 2 c − O ϵ ( n log n ) ≤ − log P ϵ s e c ( N ) ≤ log L ϵ s e c ( N ) ≤ n 2 − n log n c + O ϵ ( n ) . \frac{n^2}{c}-O_\epsilon(n\log n)\le-\log P^{\mathrm{sec}}_\epsilon(N)\le\log L^{\mathrm{sec}}_\epsilon(N)\le\frac{n^2-n\log n}{c}+O_\epsilon(n). c n 2 − O ϵ ( n log n ) ≤ − log P ϵ sec ( N ) ≤ log L ϵ sec ( N ) ≤ c n 2 − n log n + O ϵ ( n ) . The lower bound holds for binary matrices of value exactly $1/2.
Proof. For the upper bound sample r = ⌈ ( n + 1 ) / c ⌉ r=\lceil(n+1)/c\rceil r = ⌈( n + 1 ) / c ⌉ times from an optimal column strategy. The bounded-variable Chernoff bound gives probability at most 2 − c r 2^{-cr} 2 − cr that a fixed row exceeds β \beta β . Thus the list of the ( N + r − 1 r ) \binom{N+r-1}{r} ( r N + r − 1 ) empirical strategies contains a successful one. Its logarithm is r n − r log r + O ( r ) rn-r\log r+O(r) r n − r log r + O ( r ) by Stirling’s formula. Drawing uniformly from a universal list succeeds with probability at least the reciprocal of its size.
For the lower bound choose a uniform set C C C of K = 2 ⌈ n 8 / 2 ⌉ K=2\lceil n^8/2\rceil K = 2 ⌈ n 8 /2 ⌉ columns, for N N N sufficiently large. Choose ⌊ N / 2 ⌋ \lfloor N/2\rfloor ⌊ N /2 ⌋ independent uniform K / 2 K/2 K /2 -subsets of C C C . Each supplies two rows, its indicator on C C C and the complementary indicator, both equal to one outside C C C . Duplicate the first row if N N N is odd. The uniform strategy on C C C pays exactly 1 / 2 1/2 1/2 on every row. A uniformly random member of any row pair earns at least 1 / 2 1/2 1/2 on every column. Hence the value is 1 / 2 1/2 1/2 .
Fix any proposed distribution p p p . Its heavy set H 0 = { j : p j ≥ 1 / ( K N 2 ) } H_0=\{j:p_j\ge1/(KN^2)\} H 0 = { j : p j ≥ 1/ ( K N 2 )} has size at most K N 2 KN^2 K N 2 . Write H = H 0 ∩ C H=H_0\cap C H = H 0 ∩ C , h = ∣ H ∣ h=|H| h = ∣ H ∣ . The planted mass outside H H H is at most n − 2 n^{-2} n − 2 . Conditional on C C C , let $Z be the payoff of the first row in one pair against p p p . Given that the row contains exactly k k k ones on H H H , exchangeability gives
E [ Z ∣ k , C ] ≥ ( k / h ) p ( H ) + p ( C c ) ≥ k / h − n − 2 ( h > 0 ) . \mathbb{E}[Z \mid k,C] \ge(k/h)p(H) + p(C^{\mathrm{c}}) \ge k/h - n^{-2} \qquad(h>0). E [ Z ∣ k , C ] ≥ ( k / h ) p ( H ) + p ( C c ) ≥ k / h − n − 2 ( h > 0 ) .
For h = O ϵ ( n ) h = O_{\epsilon}(n) h = O ϵ ( n ) large enough, take k = ⌈ β h ⌉ + 1 ≤ h k = \lceil\beta h\rceil+ 1 \le h k = ⌈ β h ⌉ + 1 ≤ h . Since 0 ≤ Z ≤ 1 0 \le Z \le1 0 ≤ Z ≤ 1 , this gives Pr [ Z > β ∣ k , C ] = Ω ϵ ( 1 / h ) \Pr[Z > \beta\mid k,C] = \Omega_{\epsilon}(1/h) Pr [ Z > β ∣ k , C ] = Ω ϵ ( 1/ h ) . The probability of this hypergeometric layer is at least ( h k ) 2 − h exp ( − O ( h 2 / K ) ) \binom{h}{k}2^{-h}\exp(-O(h^2/K)) ( k h ) 2 − h exp ( − O ( h 2 / K )) : the probability of any fixed pattern is ( K / 2 ) k ( K / 2 ) h − k / ( K ) h (K/2)_k(K/2)_{h-k}/(K)_h ( K /2 ) k ( K /2 ) h − k / ( K ) h , using falling factorials. The binomial entropy estimate gives Pr [ Z > β ∣ C ] ≥ 2 − c h − O ϵ ( log ( h + 2 ) ) \Pr[Z > \beta\mid C] \ge2^{-ch-O_{\epsilon}(\log(h+2))} Pr [ Z > β ∣ C ] ≥ 2 − c h − O ϵ ( l o g ( h + 2 )) . For bounded positive h h h use the all-ones pattern, and for h = 0 h=0 h = 0 the outside mass exceeds β \beta β .
Choose h 0 = ⌊ ( n − B ϵ log n ) / c ⌋ h_0 = \lfloor(n-B_{\epsilon}\log n)/c\rfloor h 0 = ⌊( n − B ϵ log n ) / c ⌋ with B ϵ B_{\epsilon} B ϵ sufficiently large. When h < h 0 h<h_0 h < h 0 the ⌊ N / 2 ⌋ \lfloor N/2\rfloor ⌊ N /2 ⌋ independent first rows reject p p p except with probability exp ( − Ω ( n 3 ) ) \exp(-\Omega(n^3)) exp ( − Ω ( n 3 )) . Otherwise a union bound gives
Pr C [ h ≥ h 0 ] ≤ ( K n 2 h 0 ) ( K / N ) h 0 ≤ 2 − n 2 / c + O ϵ ( n log n ) . \Pr_C[h \ge h_0] \le\binom{Kn^2}{h_0}(K/N)^{h_0} \le2^{-n^2/c+O_{\epsilon}(n\log n)}. C Pr [ h ≥ h 0 ] ≤ ( h 0 K n 2 ) ( K / N ) h 0 ≤ 2 − n 2 / c + O ϵ ( n l o g n ) .
Averaging over arbitrary game-independent proposals proves the lower bound. □ \square □
Symmetric games with arbitrary payoffs
For a symmetric bimatrix game let A ∈ [ 0 , 1 ] N × N A \in[0,1]^{N\times N} A ∈ [ 0 , 1 ] N × N be arbitrary. The two payoffs at ( i , j ) (i,j) ( i , j ) are A i j A_{ij} A ij and A j i A_{ji} A j i . Write P ϵ s y m ( N ) P_{\epsilon}^{\mathrm{sym}}(N) P ϵ sym ( N ) and L ϵ s y m ( N ) L_{\epsilon}^{\mathrm{sym}}(N) L ϵ sym ( N ) for the proposal probability and list size in Theorem 3.1 with this larger class of games. Both players may again use arbitrary mixed strategies in a proposal.
Theorem A.4. For every fixed 0 < ϵ < 1 / 2 0<\epsilon<1/2 0 < ϵ < 1/2 , with n = log N n=\log N n = log N ,
1 4 [ 1 − H 2 ( 1 / 2 + ϵ ) ] ≤ lim inf N → ∞ − log P ϵ s y m ( N ) n 2 ≤ lim sup N → ∞ log L ϵ s y m ( N ) n 2 ≤ ln 2 8 ϵ 2 . \frac{1}{4[1-H_2(1/2+\epsilon)]}
\le\liminf_{N\to\infty}\frac{-\log P_{\epsilon}^{\mathrm{sym}}(N)}{n^2}
\le\limsup_{N\to\infty}\frac{\log L_{\epsilon}^{\mathrm{sym}}(N)}{n^2}
\le\frac{\ln2}{8\epsilon^2}. 4 [ 1 − H 2 ( 1/2 + ϵ )] 1 ≤ N → ∞ lim inf n 2 − log P ϵ sym ( N ) ≤ N → ∞ lim sup n 2 log L ϵ sym ( N ) ≤ 8 ϵ 2 ln 2 . If ϵ = ϵ ( N ) → 0 \epsilon=\epsilon(N)\to0 ϵ = ϵ ( N ) → 0 and log ( 1 / ϵ ) = o ( n ) \log(1/\epsilon)=o(n) log ( 1/ ϵ ) = o ( n ) , both quantities have the same leading term:
− log P ϵ s y m ( N ) = ( ln 2 8 + o ( 1 ) ) n 2 ϵ 2 , log L ϵ s y m ( N ) = ( ln 2 8 + o ( 1 ) ) n 2 ϵ 2 . -\log P_{\epsilon}^{\mathrm{sym}}(N)
=\left(\frac{\ln2}{8}+o(1)\right)\frac{n^2}{\epsilon^2},
\qquad
\log L_{\epsilon}^{\mathrm{sym}}(N)
=\left(\frac{\ln2}{8}+o(1)\right)\frac{n^2}{\epsilon^2}. − log P ϵ sym ( N ) = ( 8 ln 2 + o ( 1 ) ) ϵ 2 n 2 , log L ϵ sym ( N ) = ( 8 ln 2 + o ( 1 ) ) ϵ 2 n 2 . Proof. The lower bounds follow by restricting the games to the constant-sum subclass. We prove the upper bound directly. For a common mixed action p p p let u ( p ) = p T A p u(p)=p^{\mathsf{T}}Ap u ( p ) = p T A p be the payoff at ( p , p ) (p,p) ( p , p ) . A symmetric proposal ( z , z ) (z,z) ( z , z ) has regret max i ( A z ) i − u ( z ) \max_i(Az)_i-u(z) max i ( A z ) i − u ( z ) for either player. Unlike the constant-sum case, its baseline u ( z ) u(z) u ( z ) varies with the sample.
Take n n n large and put
Δ = ϵ n − 1 / 4 , e = ϵ − Δ , t = 4 e , d = 2 e 2 / ln 2. \Delta=\epsilon n^{-1/4},\qquad e=\epsilon-\Delta,\qquad t=4e,\qquad d=2e^2/\ln2. Δ = ϵ n − 1/4 , e = ϵ − Δ , t = 4 e , d = 2 e 2 / ln 2. Use the continuous functions
q p ( i ) = exp [ − t ( u ( p ) + e ) ] ( 1 + ( exp t − 1 ) ( A p ) i ) . q_p(i)=\exp[-t(u(p)+e)]\bigl(1+(\exp t-1)(Ap)_i\bigr). q p ( i ) = exp [ − t ( u ( p ) + e )] ( 1 + ( exp t − 1 ) ( A p ) i ) . If X X X is Bernoulli with mean u ( p ) u(p) u ( p ) , then ∑ i p i q p ( i ) = e − t e E exp ( t ( X − E X ) ) \sum_i p_iq_p(i)=e^{-te}\mathbb{E}\exp(t(X-\mathbb{E}X)) ∑ i p i q p ( i ) = e − t e E exp ( t ( X − E X )) . Hoeffding’s lemma gives
∑ i p i q p ( i ) ≤ exp ( − t e + t 2 / 8 ) = 2 − d . \sum_i p_iq_p(i)\le\exp(-te+t^2/8)=2^{-d}. i ∑ p i q p ( i ) ≤ exp ( − t e + t 2 /8 ) = 2 − d .
Lemma 2.1 applies with d d d in place of c c c . Indeed, the first coordinate at a fixed point gives
N − 1 / J ≤ Z − 1 / J ∑ i p i q p ( i ) ≤ Z − 1 / J 2 − d . N^{-1/J} \le Z^{-1/J}\sum_i p_iq_p(i) \le Z^{-1/J}2^{-d}. N − 1/ J ≤ Z − 1/ J i ∑ p i q p ( i ) ≤ Z − 1/ J 2 − d .
Thus the same endpoint argument yields Z = 1 / 2 Z = 1/2 Z = 1/2 , positive J ≤ ( n + 1 ) / d J \le(n+1)/d J ≤ ( n + 1 ) / d , and
p i = q p ( i ) J / Z , q p ( i ) < 1 , ∑ i p i 1 + 1 / J ≤ 2 1 / J − d . p_i = q_p(i)^{J}/Z,\qquad q_p(i) < 1,\qquad\sum_i p_i^{1+1/J} \le2^{1/J-d}. p i = q p ( i ) J / Z , q p ( i ) < 1 , i ∑ p i 1 + 1/ J ≤ 2 1/ J − d .
Put r 0 = ⌈ 32 / Δ 2 ⌉ r_0 = \lceil32/\Delta^2\rceil r 0 = ⌈ 32/ Δ 2 ⌉ and r = max { ⌈ J ⌉ , r 0 } r = \max\{\lceil J\rceil,r_0\} r = max {⌈ J ⌉ , r 0 } . Draw r r r actions independently from p p p and let z z z be their empirical distribution. The exponential Markov argument of Lemma 3.2 now bounds Pr [ max i ( A z ) i > u ( p ) + e ] \Pr[\max_i(Az)_i > u(p)+e] Pr [ max i ( A z ) i > u ( p ) + e ] by ∑ i q p ( i ) r ≤ 1 / 2 \sum_i q_p(i)^r \le1/2 ∑ i q p ( i ) r ≤ 1/2 . It remains to bound the common payoff u ( z ) u(z) u ( z ) . Expanding its double sum over the sampled actions gives
E u ( z ) = ( 1 − 1 / r ) u ( p ) + ( 1 / r ) ∑ i p i A i i . \mathbb{E}u(z) = (1-1/r)u(p) + (1/r)\sum_i p_iA_{ii}. E u ( z ) = ( 1 − 1/ r ) u ( p ) + ( 1/ r ) i ∑ p i A ii .
Its bias is at most 1 / r 1/r 1/ r . Changing one sampled action changes u ( z ) u(z) u ( z ) by at most 2 / r 2/r 2/ r , since only terms involving its index can change. As 1 / r ≤ Δ / 2 1/r \le\Delta/2 1/ r ≤ Δ/2 , the bounded-difference inequality gives
Pr [ u ( z ) < u ( p ) − Δ ] ≤ exp ( − r Δ 2 / 8 ) < 1 / 4. \Pr[u(z) < u(p)-\Delta] \le\exp(-r\Delta^2/8) < 1/4. Pr [ u ( z ) < u ( p ) − Δ ] ≤ exp ( − r Δ 2 /8 ) < 1/4.
Thus at least a quarter of the product measure consists of successful tuples.
When r = ⌈ J ⌉ r=\lceil J\rceil r = ⌈ J ⌉ , Hölder’s inequality as in Lemma 3.2 gives at least 2 d r 2 − O ( r + 1 ) 2^{dr^2-O(r+1)} 2 d r 2 − O ( r + 1 ) successful tuples, with an absolute implicit constant for 0 < ϵ ≤ 1 / 2 0<\epsilon\le1/2 0 < ϵ ≤ 1/2 . Their ambient density is at least 2 − n r 2 / ( 4 d ) − O ( n / d ) 2^{-nr^2/(4d)-O(n/d)} 2 − n r 2 / ( 4 d ) − O ( n / d ) . If r = r 0 > ⌈ J ⌉ r=r_0>\lceil J\rceil r = r 0 > ⌈ J ⌉ , the existence of even one successful tuple gives ambient density at least 2 − n r 0 2^{-nr_0} 2 − n r 0 . Here n r 0 = O ( n 3 / 2 / ϵ 2 ) = o ( n 2 / ϵ 2 ) nr_0=O(n^{3/2}/\epsilon^2)=o(n^2/\epsilon^2) n r 0 = O ( n 3/2 / ϵ 2 ) = o ( n 2 / ϵ 2 ) , uniformly in ϵ \epsilon ϵ . An oblivious sampler chooses the length uniformly through max { ⌈ ( n + 1 ) / d ⌉ , r 0 } \max\{\lceil(n+1)/d\rceil,r_0\} max {⌈( n + 1 ) / d ⌉ , r 0 } and samples a uniform ambient tuple. The cost of guessing the length in the exponent is O ( log ( n + 2 ) + log ( 1 / ϵ ) ) O(\log(n+2)+\log(1/\epsilon)) O ( log ( n + 2 ) + log ( 1/ ϵ )) . Since d = ( 2 ϵ 2 / ln 2 ) ( 1 − n − 1 / 4 ) 2 d=(2\epsilon^2/\ln2)(1-n^{-1/4})^2 d = ( 2 ϵ 2 / ln 2 ) ( 1 − n − 1/4 ) 2 , these bounds give the claimed upper coefficient.
For a universal list, round entries of A A A to a grid of denominator D = ⌈ n / ϵ ⌉ D=\lceil n/\epsilon\rceil D = ⌈ n / ϵ ⌉ . Each player’s expected payoff and its best-deviation payoff each change by at most 1 / D 1/D 1/ D . Apply the sampler to the rounded games with tolerance ϵ − 2 / D = ϵ ( 1 − O ( 1 / n ) ) \epsilon-2/D=\epsilon(1-O(1/n)) ϵ − 2/ D = ϵ ( 1 − O ( 1/ n )) . There are at most ( D + 1 ) N 2 (D+1)^{N^2} ( D + 1 ) N 2 such games. As in Theorem 3.1 , sampling a finite list adds at most 2 n + O ( log log ( D + 1 ) ) 2n+O(\log\log(D+1)) 2 n + O ( log log ( D + 1 )) bits to the logarithm of its size. This preserves the stated leading terms.
General bimatrix games
Let P ϵ b i ( N ) P^{\mathrm{bi}}_\epsilon(N) P ϵ bi ( N ) and L ϵ b i ( N ) L^{\mathrm{bi}}_\epsilon(N) L ϵ bi ( N ) denote the oblivious success probability and universal list size for ordinary additive ϵ \epsilon ϵ -Nash equilibria of games with two arbitrary payoff matrices A , B ∈ [ 0 , 1 ] N × N A,B\in[0,1]^{N\times N} A , B ∈ [ 0 , 1 ] N × N , in row and column order.
Theorem A.5. Write n = log N n=\log N n = log N . For every fixed 0 < ϵ < 1 / 2 0<\epsilon<1/2 0 < ϵ < 1/2 , and also for ϵ → 0 \epsilon\to0 ϵ → 0 with log ( 1 / ϵ ) = o ( n ) \log(1/\epsilon)=o(n) log ( 1/ ϵ ) = o ( n ) ,
− log P ϵ b i ( N ) ≤ log L ϵ b i ( N ) ≤ ( ln 2 2 + o ( 1 ) ) n 2 ϵ 2 . -\log P^{\mathrm{bi}}_\epsilon(N)\le\log L^{\mathrm{bi}}_\epsilon(N)\le\left(\frac{\ln2}{2}+o(1)\right)\frac{n^2}{\epsilon^2}. − log P ϵ bi ( N ) ≤ log L ϵ bi ( N ) ≤ ( 2 ln 2 + o ( 1 ) ) ϵ 2 n 2 .
Proof. Put Δ = ϵ n − 1 / 4 \Delta=\epsilon n^{-1/4} Δ = ϵ n − 1/4 , e = ϵ − Δ e=\epsilon-\Delta e = ϵ − Δ , t = 4 e t=4e t = 4 e , d = 2 e 2 / ln 2 d=2e^2/\ln2 d = 2 e 2 / ln 2 , and ζ = 1 / 8 \zeta=1/8 ζ = 1/8 . For mixed strategies p , q p,q p , q write a = p T A q a=p^{\mathsf T}Aq a = p T A q , b = p T B q b=p^{\mathsf T}Bq b = p T B q and define
g i = ∑ j q j exp ( t ( A i j − a − e ) ) , h j = ∑ i p i exp ( t ( B i j − b − e ) ) . g_i=\sum_j q_j\exp(t(A_{ij}-a-e)),\qquad h_j=\sum_i p_i\exp(t(B_{ij}-b-e)). g i = j ∑ q j exp ( t ( A ij − a − e )) , h j = i ∑ p i exp ( t ( B ij − b − e )) .
Under p ⊗ q p\otimes q p ⊗ q each payoff has range in [ 0 , 1 ] [0,1] [ 0 , 1 ] and mean equal to its baseline. Hoeffding’s lemma gives
∑ i p i g i , ∑ j q j h j ≤ exp ( − t e + t 2 / 8 ) = 2 − d . \sum_i p_i g_i,\ \sum_j q_j h_j\le\exp(-te+t^2/8)=2^{-d}. i ∑ p i g i , j ∑ q j h j ≤ exp ( − t e + t 2 /8 ) = 2 − d .
There are p p p , q q q and J , L > 0 J,L>0 J , L > 0 satisfying
Z = ∑ i g i J = ζ , W = ∑ j h j L = ζ , p i = g i J / Z , q j = h j L / W . Z=\sum_i g_i^J=\zeta,\qquad W=\sum_j h_j^L=\zeta,\qquad p_i=g_i^J/Z,\quad q_j=h_j^L/W. Z = i ∑ g i J = ζ , W = j ∑ h j L = ζ , p i = g i J / Z , q j = h j L / W .
Indeed put U = ( n + 4 ) / d U=(n+4)/d U = ( n + 4 ) / d and apply Brouwer on Δ N 2 × [ 0 , U ] 2 \Delta_N^2\times[0,U]^2 Δ N 2 × [ 0 , U ] 2 . Normalize the two power vectors for the first two coordinates, and project J + log ( Z / ζ ) J+\log(Z/\zeta) J + log ( Z / ζ ) and L + log ( W / ζ ) L+\log(W/\zeta) L + log ( W / ζ ) onto [ 0 , U ] [0,U] [ 0 , U ] for the last two. All entries are positive and continuous. At exponent zero its sum is N N N , so its coordinate increases. At a fixed point with J > 0 J>0 J > 0 ,
2 − n / J ≤ ∑ i p i 1 + 1 / J = Z − 1 / J ∑ i p i g i ≤ Z − 1 / J 2 − d , 2^{-n/J}\leq\sum_i p_i^{1+1/J}=Z^{-1/J}\sum_i p_i g_i\leq Z^{-1/J}2^{-d}, 2 − n / J ≤ i ∑ p i 1 + 1/ J = Z − 1/ J i ∑ p i g i ≤ Z − 1/ J 2 − d ,
which gives Z ≤ 2 n − d J Z\leq2^{n-dJ} Z ≤ 2 n − dJ . At J = U J=U J = U this is less than ζ \zeta ζ , so that coordinate decreases. The same inequalities hold for L , W L,W L , W . Both exponents are therefore interior, and their fixed-point equations give the claimed normalizations. In particular J , L ≤ ( n + 3 ) / d J,L\leq(n+3)/d J , L ≤ ( n + 3 ) / d and g i , h j < 1 g_i,h_j<1 g i , h j < 1 .
Put m 0 = ⌈ 16 / Δ 2 ⌉ m_0=\lceil16/\Delta^2\rceil m 0 = ⌈ 16/ Δ 2 ⌉ . Draw s = max { ⌈ L ⌉ , m 0 } s=\max\{\lceil L\rceil,m_0\} s = max {⌈ L ⌉ , m 0 } row actions from p p p and r = max { ⌈ J ⌉ , m 0 } r=\max\{\lceil J\rceil,m_0\} r = max {⌈ J ⌉ , m 0 } column actions from q q q , all independently. For the empirical profile ( x , y ) (x,y) ( x , y ) , exponential Markov and a union bound give
Pr [ max i ( A y ) i > a + ϵ ] ≤ ∑ i g i r ≤ ζ , Pr [ max j ( x T B ) j > b + ϵ ] ≤ ∑ j h j s ≤ ζ . \Pr[\max_i(Ay)_i>a+\epsilon]\leq\sum_i g_i^r\leq\zeta,\qquad
\Pr[\max_j(x^\mathsf{T}B)_j>b+\epsilon]\leq\sum_j h_j^s\leq\zeta. Pr [ i max ( A y ) i > a + ϵ ] ≤ i ∑ g i r ≤ ζ , Pr [ j max ( x T B ) j > b + ϵ ] ≤ j ∑ h j s ≤ ζ .
The payoffs x T A y , x T B y x^\mathsf{T}Ay,x^\mathsf{T}By x T A y , x T B y have means a , b a,b a , b . Changing a sampled row or column action changes either payoff by at most 1 / s 1/s 1/ s or 1 / r 1/r 1/ r , respectively. The bounded-difference inequality therefore bounds each lower tail at distance Δ \Delta Δ by exp ( − 2 Δ 2 / ( 1 / s + 1 / r ) ) ≤ e − 16 \exp(-2\Delta^2/(1/s+1/r))\leq e^{-16} exp ( − 2 Δ 2 / ( 1/ s + 1/ r )) ≤ e − 16 . With probability at least 1 / 2 1/2 1/2 the empirical pair is an ϵ \epsilon ϵ -Nash equilibrium.
Row tuples whose conditional success probability is at least 1 / 4 1/4 1/4 have p ⊗ s p^{\otimes s} p ⊗ s -mass at least 1 / 3 1/3 1/3 . Hölder and the displayed power-moment bound give at least
( 1 / 3 ) J + 1 ( ∑ i p i 1 + 1 / J ) − s J ≥ ( 1 / 3 ) J + 1 ζ s 2 d J s (1/3)^{J+1}\left(\sum_i p_i^{1+1/J}\right)^{-sJ}\geq(1/3)^{J+1}\zeta^{s}2^{dJs} ( 1/3 ) J + 1 ( i ∑ p i 1 + 1/ J ) − s J ≥ ( 1/3 ) J + 1 ζ s 2 dJ s
such rows. For each of them the same argument gives at least ( 1 / 4 ) L + 1 ζ r 2 d L r (1/4)^{L+1}\zeta^r2^{dLr} ( 1/4 ) L + 1 ζ r 2 d L r successful column tuples. Thus the negative logarithm of the density among ambient ordered tuples is at most
n ( s + r ) − d ( J s + L r ) + O ( J + L + s + r + 1 ) ≤ n ( J + L ) − 2 d J L + O ( n m 0 + n / d ) . n(s+r)-d(Js+Lr)+O(J+L+s+r+1)\leq n(J+L)-2dJL+O(nm_0+n/d). n ( s + r ) − d ( J s + L r ) + O ( J + L + s + r + 1 ) ≤ n ( J + L ) − 2 dJ L + O ( n m 0 + n / d ) .
The cross term reflects the two roles of J J J : it supplies the entropy bound on row actions and the sample length for column actions. The bilinear expression is largest at a corner of [ 0 , ( n + 3 ) / d ] 2 [0,(n+3)/d]^2 [ 0 , ( n + 3 ) / d ] 2 , where it is at most n ( n + 3 ) / d n(n+3)/d n ( n + 3 ) / d . Guessing both lengths uniformly up to max { ⌈ ( n + 3 ) / d ⌉ , m 0 } \max\{\lceil(n+3)/d\rceil,m_0\} max {⌈( n + 3 ) / d ⌉ , m 0 } costs O ( log ( n + 2 ) + log ( 1 / ϵ ) ) O(\log(n+2)+\log(1/\epsilon)) O ( log ( n + 2 ) + log ( 1/ ϵ )) additional bits in the exponent. Since n m 0 = O ( n 3 / 2 / ϵ 2 ) nm_0=O(n^{3/2}/\epsilon^2) n m 0 = O ( n 3/2 / ϵ 2 ) , this proves the probability bound with the stated coefficient.
For the list, discretize both payoff matrices on a grid with denominator D = ⌈ n / ϵ ⌉ D=\lceil n/\epsilon\rceil D = ⌈ n / ϵ ⌉ . Each deviation gain changes by at most 2 / D 2/D 2/ D . Use the sampler at tolerance ϵ − 2 / D \epsilon-2/D ϵ − 2/ D and take independent proposals to hit every rounded game. There are at most ( D + 1 ) 2 N 2 (D+1)^{2N^2} ( D + 1 ) 2 N 2 games on the grid. The logarithm of the required list size exceeds the negative logarithm of single-proposal success by at most 2 n + O ( log log ( D + 1 ) + 1 ) 2n+O(\log\log(D+1)+1) 2 n + O ( log log ( D + 1 ) + 1 ) , which preserves the leading term. □
Remark A.6. (The bimatrix gap). Theorem A.5 has no matching lower bound. Zero-sum games give one: if B = 11 T − A B=\mathbf{1}\mathbf{1}^{\mathsf{T}}-A B = 1 1 T − A and A A A has value $1/2$, an ϵ \epsilon ϵ -Nash pair ( x , y ) (x,y) ( x , y ) satisfies $\max_i(Ay)_i\leq u+\epsilon and min j ( x T A ) j ≥ u − ϵ \min_j (x^{T}A)_j \ge u-\epsilon min j ( x T A ) j ≥ u − ϵ , so u ≤ 1 / 2 + ϵ u \le1/2+\epsilon u ≤ 1/2 + ϵ and y y y is 2 ϵ 2\epsilon 2 ϵ -secure. Theorem A.3 at accuracy 2 ϵ 2\epsilon 2 ϵ therefore gives − log P ϵ B i ( N ) ≥ n 2 / c 2 ϵ − O ϵ ( n log n ) -\log P^{\mathrm{Bi}}_{\epsilon}(N) \ge n^2/c_{2\epsilon}-O_{\epsilon}(n\log n) − log P ϵ Bi ( N ) ≥ n 2 / c 2 ϵ − O ϵ ( n log n ) , which is ( ln 2 / 8 + o ( 1 ) ) n 2 / ϵ 2 (\ln2/8+o(1))n^2/\epsilon^2 ( ln 2/8 + o ( 1 )) n 2 / ϵ 2 for small ϵ \epsilon ϵ . A factor four remains between this and the upper bound, and we do not know the sharp constant for general bimatrix games.
Remark A.7 (The Daskalakis–Papadimitriou packing for ordinary regret). In the hard family of [DP09, Section 3], each game hides an even-sized set S S S of ℓ \ell ℓ rows among N = ( ℓ ℓ / 2 ) N=\binom{\ell}{\ell/2} N = ( ℓ /2 ℓ ) rows. The columns are indexed by the half-size subsets T T T of S S S . Change the row payoff outside S S S from − 1 -1 − 1 to 0 0 0 . The resulting payoffs are ( 1 i ∈ T , 1 − 1 i ∈ T ) (1_{i\in T},1-1_{i\in T}) ( 1 i ∈ T , 1 − 1 i ∈ T ) at every entry ( i , T ) (i,T) ( i , T ) . The uniform row strategy u S u_S u S earns 1 / 2 1/2 1/2 against every column. At an ordinary ϵ \epsilon ϵ -Nash profile with row marginal x x x , the row player therefore earns at least 1 / 2 − ϵ 1/2-\epsilon 1/2 − ϵ . The column player’s regret bound then gives x ( T ) ≥ 1 / 2 − 2 ϵ x(T)\ge1/2-2\epsilon x ( T ) ≥ 1/2 − 2 ϵ for every T T T .
Let D = ∑ i ∈ S ( 1 / ℓ − x i ) + = ∥ x − u S ∥ 1 / 2 D=\sum_{i\in S}(1/\ell-x_i)_+=\|x-u_S\|_1/2 D = ∑ i ∈ S ( 1/ ℓ − x i ) + = ∥ x − u S ∥ 1 /2 . The largest ℓ / 2 \ell/2 ℓ /2 numbers 1 / ℓ − x i 1/\ell-x_i 1/ ℓ − x i sum to at least D / 2 D/2 D /2 . Indeed, if at least half are positive, the largest half captures at least half their sum. Otherwise, filling the half-set with the least negative entries uses at most half the total negative mass, which is at most D D D since ∑ i ∈ S ( 1 / ℓ − x i ) = 1 − x ( S ) ≥ 0 \sum_{i\in S}(1/\ell-x_i)=1-x(S)\ge0 ∑ i ∈ S ( 1/ ℓ − x i ) = 1 − x ( S ) ≥ 0 . For this half-set T T T we have D / 2 ≤ 1 / 2 − x ( T ) ≤ 2 ϵ D/2\le1/2-x(T)\le2\epsilon D /2 ≤ 1/2 − x ( T ) ≤ 2 ϵ . Thus ∥ x − u S ∥ 1 ≤ 8 ϵ \|x-u_S\|_1\le8\epsilon ∥ x − u S ∥ 1 ≤ 8 ϵ . Claim 3 of [DP09] packs Ω ( 2 ( 0.8 − 34 ϵ ) n 2 ) \Omega(2^{(0.8-34\epsilon)n^2}) Ω ( 2 ( 0.8 − 34 ϵ ) n 2 ) disjoint balls of this radius. A proposal can succeed for at most one packed game, giving the stated lower bound for 0 < ϵ < 2 / 85 0<\epsilon<2/85 0 < ϵ < 2/85 .
AI disclosure
Claude assisted in developing the fully adaptive degree-two discovery argument, the derandomized anchor selection under H H H , and the consequences for tournaments in Section 2.1. ChatGPT (Codex) assisted in developing and checking the the blockwise derandomization, the algebraic lower bound and the oracle construction. Both assisted in drafting and revising the exposition.