One randomized recovery trial at fixed rational slack
OpenStableMSR.Recovery.Supplement.rational_single_run_programFor each fixed rational slack , there is one finite admissible distance-table RAM program, chosen before the instance, with common absolute positive constants . On every finite metric and valid exact cluster count, every tape yields a feasible output within charged steps. If the input is -stable, the probability that this single run's output differs from the optimum is at most . This is the machine implementation obligation for the rational parameter case of Theorem 4.5. Rational approximation of an arbitrary stability factor, conversion to the inverse-fifth exponent, and amplification over independent runs are handled separately.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_RandomExecution set_option autoImplicit false open scoped Classical ENNReal
Formal statement
namespace StableMSR.Recovery.Supplement
/-- A single fixed-rational-parameter trial on the public distance-table RAM. -/
theorem rational_single_run_program :
∃ a b : ℕ, 0 < a ∧ 0 < b ∧ ∀ e : ℚ, 0 < e → e < 1 →
∃ P : MinSumFPT.Program, MinSumFPT.Admissible P ∧
∀ (n k : ℕ) (d : Point n → Point n → ℝ), 1 ≤ k → k ≤ n → IsMetricArray d →
let T := a*n^(b*parameterEnvelope (e:ℝ))
AlwaysFeasible P n k d T ∧ ∀ O : Partition n,
Stable d k (1+(e:ℝ)) O →
MinSumFPT.tapeLaw {ω | randomOutput P n k d T ω ≠ O} ≤ (2/3 : ENNReal) := by sorry
end StableMSR.Recovery.Supplement
Source