Complete-table compatible-set squared radius
DefinitionRankingQueryCost_Joint_Supplement_Radiusp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1persistent-faultsquery-complexityranking
Let be a complete comparison table on objects and its compatible rank permutations. Centers range over the full continuous output polytope , including ties and nonintegral coordinates. Define
For nonempty compatible sets, compactness of and finiteness of the ranks make these extrema attained. The extended nonnegative real encoding assigns zero to the supremum of an empty compatible set. All source radius claims concern nonempty compatible sets. This is an operational radius, independent of the target formula .
Definition code
import Definitions.Def_RankingQueryCost_Joint_Transcript
set_option autoImplicit false
noncomputable section
namespace RankingQueryCost.Joint.Supplement
/-- §2.2: squared radius of the complete-table version space, with centers in the
entire continuous output polytope. Extended nonnegative reals make both optima total.
The supremum of an empty compatible set is zero. The theorems use nonempty sets. -/
def radius {n : ℕ} (s : ℕ) (T : Tournament n) : ENNReal :=
⨅ q : {q // q ∈ estimateSet n},
⨆ r : {r // r ∈ compatible s (completeTranscript T)},
ENNReal.ofReal (squaredError q.val (rankVector r.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