Theorem 4.13 — A single problem-independent Q(∆,k)=∆^{O(4^k)} bounds error-free per-vertex expectation and the full tail with logarithmic power 2^{k−1}.
OpenGreedyColoringLCA969.LowerBound.Supplement.theorem_4_13graph-theorylocal-computationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
There are a universal function and an absolute integer with
For every finite label set , every extendable and radius-one locally verifiable -labeling problem on all finite simple graphs, and every integer , there is one error-free standard-oracle LCA such that for every representation of a graph of maximum degree at most and every vertex ,
and, for every real ,
The same algorithm gives the expectation bound and every tail bound. The function and its exponent constant precede the problem; the algorithm can depend on the problem and degree bound, but not on the graph or . Realizability of every label is not a hypothesis. The existence of the extension rule forces nonempty, including the one-label case.
Differences from the source:
- encoding: vertices 1 through n and L-valued answers in the standard adjacency-list model → Fin n identifiers and injective positive-integer return codes, with success and cost derived from the immutable shared-tape execution; reason: shifting identifiers and coding labels preserves every graph, list order, question and graph-query count
- encoding: Q on positive integer pairs with growth Delta^{O(4^k)} → Q on natural pairs, at least one everywhere, and an absolute c>=1 bounding Q by Delta^(c*4^k) for Delta>=2,k>=1; reason: values at zero can be set to one without changing a source instance; the absolute exponent is quantified in the proof on pp.26–27
- encoding: expected and high-probability query counts → nonnegative extended expectation and actual execution-cost events; reason: nontermination has infinite cost, and the same algorithm is selected before every epsilon
Preamble
import Definitions.Def_GreedyColoringLCA969_LowerBound_Supplement_LabelPerformance open scoped ENNReal BigOperators open MeasureTheory Classical set_option autoImplicit false
Formal statement
namespace GreedyColoringLCA969.LowerBound.Supplement
theorem theorem_4_13 :
∃ (Q : ℕ → ℕ → ℝ) (c : ℕ), 1 ≤ c ∧
(∀ Δ k, 1 ≤ Q Δ k) ∧
(∀ Δ k : ℕ, 2 ≤ Δ → 1 ≤ k → Q Δ k ≤ (Δ : ℝ)^(c * 4^k)) ∧
∀ (L : Type) [Fintype L] (P : LabelProblem L) (F : Multiset L → L)
(C : Set (L × Multiset L)), IsExtensionRule P F → IsLocalVerifier P C →
∀ Δ : ℕ, 2 ≤ Δ → ∃ A : Algorithm .standard,
ErrorFreeOn P (finiteCode L) A Δ ∧
∀ (n : ℕ) (R : Representation n), MaxDegreeAtMost R.graph Δ → ∀ v,
expectedQueries A R v ≤ ENNReal.ofReal (Q Δ (Fintype.card L)) ∧
∀ ε : ℝ, 0 < ε → ε ≤ 1 / 2 →
ENNReal.ofReal (1 - ε) ≤ tapeLaw {r | queryCost A R r v ≤
ENNReal.ofReal (Q Δ (Fintype.card L) *
(log2 (1 / ε))^(2^(Fintype.card L - 1)))} := by sorry
end GreedyColoringLCA969.LowerBound.Supplement
Source
Zi Song Yeoh, Krzysztof Onak, Dragos-Florian Ristache, STOC 2027 submission #969 (October 2026), p. 23 (PDF 24), Theorem 4.13