Full-information actual squared-error threshold
DefinitionRankingQueryCost_Joint_Supplement_ActualThresholdp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1persistent-faultsquery-complexityranking
Let be the output distribution of a randomized full-information estimator on a complete table . The optimal actual squared-error threshold is
Outputs range over all continuous estimates in . The same kernel must succeed in every complete-table world, so a true rank is not an input to the estimator. The infimum is taken in the extended nonnegative reals; infeasibility would have value . In fact bounded and a constant fallback estimator make the feasible set nonempty with finite targets.
Definition code
import Definitions.Def_RankingQueryCost_Joint_Supplement_FullEstimator
set_option autoImplicit false
noncomputable section
namespace RankingQueryCost.Joint.Supplement
/-- §2.2: infimum of attainable squared-error targets at success probability 3/4.
Every complete-table world is tested, with the same estimator law for a shared table.
An empty feasible set would give +∞, never an artificial real infimum of zero. -/
def actualThreshold (n s : ℕ) : ENNReal :=
sInf {S : ENNReal | ∃ K : FullEstimator n,
∀ (T : Tournament n) (r : Rank n), r ∈ compatible s (completeTranscript T) →
(3 / 4 : ENNReal) ≤ K.law T
{q | ENNReal.ofReal (squaredError q.val (rankVector r)) ≤ S}}
end RankingQueryCost.Joint.Supplement
Source
Chaoqiang Fu, Yifan Su, Daofeng Li, STOC 2027 submission #812 (October 2026), §2.2, p. 4, PDF p. 5