Worst complete-table compatible-set radius
DefinitionRankingQueryCost_Joint_Supplement_PublicThresholdp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1persistent-faultsquery-complexityranking
For each complete comparison table with nonempty compatible set , let be its squared radius with continuous centers in . Define
The finite table space makes this supremum a maximum. The definition uses extended nonnegative reals; a clean table always supplies a nonempty compatible set. This quantity measures full-information public uncertainty, rather than an acquisition budget.
Definition code
import Definitions.Def_RankingQueryCost_Joint_Supplement_Radius
set_option autoImplicit false
noncomputable section
namespace RankingQueryCost.Joint.Supplement
/-- §2.2: maximum complete-table radius, ranging only over nonempty version spaces.
There are finitely many tables; no asymptotic rate is built into this definition. -/
def publicThreshold (n s : ℕ) : ENNReal :=
⨆ T : {T : Tournament n // (compatible s (completeTranscript T)).Nonempty}, radius s T.val
end RankingQueryCost.Joint.Supplement
Source
Chaoqiang Fu, Yifan Su, Daofeng Li, STOC 2027 submission #812 (October 2026), §2.2, p. 4, PDF p. 5