Proposition 3.3 — Near-threshold actual accuracy
OpenRankingQueryCost.Joint.Supplement.proposition_3_3p2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1persistent-faultsquery-complexityranking
Fix . For every admissible number of objects and fixed-support budget , there is a causal algorithm returning a continuous estimate such that, in every legal world and for every allowed reply strategy,
The budget counts distinct identities on every private path, including aborts. A finite program with polynomial bit work implements the algorithm; its constants and the query constant depend only on . This is the fixed-support acquisition guarantee used by Theorem 2.1 and by the upper bounds of Theorem 2.3. A positive rational internal margin retains every real requested margin.
Differences from the source:
- encoding: n labelled objects and ranks 0 through n−1 → Fin n labels and Rank n permutations; reason: a bijective encoding preserving every instance and the full continuous output space Q
- encoding: Oδ or Θδ query rates and polynomial computation → positive constants and finite word-RAM programs quantified before n, s and the precisions; reason: makes exactly the stated uniform dependence explicit and charges computation with the published Implements contracts
- encoding: fixed real margin δ → real target δ with a rational internal δstar between δ/2 and δ; reason: a smaller internal margin gives the requested guarantee without restricting δ
Preamble
import Definitions.Def_RankingQueryCost_Joint_PublicGate set_option autoImplicit false
Formal statement
namespace RankingQueryCost.Joint.Supplement
/-- Proposition 3.3, printed p. 7 / PDF 8. The construction's free constants
are existential witnesses; the margin, success probability and hard budget are exact. -/
theorem proposition_3_3 (δ : ℝ) (hδ : 0 < δ ∧ δ ≤ 1) :
∃ (C : ℝ) (Ctime degree : ℕ) (p : ComparisonProgram) (δstar : ℚ),
0 < C ∧ 0 < Ctime ∧ 0 < δstar ∧ δ / 2 ≤ (δstar : ℝ) ∧ (δstar : ℝ) ≤ δ ∧
∀ n s : ℕ, Admissible n s → 1 ≤ s →
∃ (B : ℕ) (A : QueryPolicy n),
HardBudget s 0 B A ∧
(B : ℝ) ≤ C * resolutionCost n ((errorScale n s : ℝ) / (n : ℝ) ^ 3) ∧
PolyActual s 0 Ctime degree p δstar A ∧
(∀ W, LegalWorld s W → ∀ ω o, Returns A W 0 ω o → o.estimate ∈ estimateSet n) ∧
∀ W, LegalWorld s W →
(15 / 16 : ENNReal) ≤ privateLaw {ω | ∃ o, Returns A W 0 ω o ∧
squaredError o.estimate (rankVector W.rank) ≤ (1 + δ) * errorScale n s} := by sorry
end RankingQueryCost.Joint.Supplement
Source
Chaoqiang Fu, Yifan Su, Daofeng Li, STOC 2027 submission #812 (October 2026), Proposition 3.3, p. 7, PDF p. 8