Theorem 3.4 — Resolution-only ranking
OpenRankingQueryCost.Joint.Supplement.theorem_3_4p2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1persistent-faultsquery-complexityranking
For every fixed real there are positive constants and a causal fixed-support algorithm, uniform over admissible and public widths , with hard identity budget
In every legal world and against every allowed reply strategy, it returns a rank permutation satisfying
with probability at least . A false emission flag explicitly represents abort and never counts as successful output. A true flag always returns a permutation. The finite implementing program uses polynomial computation with constants depending only on ; its public input includes and a positive rational internal failure allowance no larger than . This resolution-only companion theorem supports the acquisition guarantee via Proposition 3.3.
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: returns a permutation or bottom on a budget abort with probability at least 1−δ of a good permutation → an emission flag separates permutation returns from aborts; ENNReal.ofReal(1−δ) is the success lower bound; reason: abort paths never count as success; for δ>1 the printed lower bound is vacuous too
Preamble
import Definitions.Def_RankingQueryCost_Joint_PublicGate set_option autoImplicit false
Formal statement
namespace RankingQueryCost.Joint.Supplement
/-- Theorem 3.4, printed p. 9 / PDF 10. The finite program is uniform in
n,s,b. Its emission bit distinguishes a returned order from a budget abort. -/
theorem theorem_3_4 (δ : ℝ) (hδ : 0 < δ) :
∃ (Cr Cq : ℝ) (Ctime degree : ℕ) (p : ComparisonProgram) (δstar : ℚ),
0 < Cr ∧ 0 < Cq ∧ 0 < Ctime ∧ 0 < δstar ∧ (δstar : ℝ) ≤ δ ∧
∀ n s b : ℕ, Admissible n s → 1 ≤ b → b ≤ n →
∃ (B : ℕ) (A : QueryPolicy n), HardBudget s 0 B A ∧
(B : ℝ) ≤ Cq * min (pairCount n : ℝ)
((n : ℝ) * (1 + Real.logb 2 ((n : ℝ) / b))) ∧
Implements s 0 Ctime degree p (estimationInput n s 0 δstar ++ [b]) A ∧
(∀ W, LegalWorld s W → ∀ ω o, Returns A W 0 ω o →
(o.emission = true → ∃ π : Rank n, o.estimate = rankVector π) ∧
(o.emission = false → o.estimate = fallback n)) ∧
∀ W, LegalWorld s W →
ENNReal.ofReal (1 - δ) ≤ privateLaw {ω | ∃ o, Returns A W 0 ω o ∧
o.emission = true ∧ ∃ π : Rank n, o.estimate = rankVector π ∧
squaredError (rankVector W.rank) (rankVector π) ≤
Cr * ((crudeScale n s : ℝ) + n * ((b : ℝ) - 1) ^ 2)} := by sorry
end RankingQueryCost.Joint.Supplement
Source
Chaoqiang Fu, Yifan Su, Daofeng Li, STOC 2027 submission #812 (October 2026), Theorem 3.4, p. 9, PDF p. 10