Lemma 5.6 (used in the proof of Theorem 1.4) — randomized path-DP terminal algorithm
OpenFasterExactColoring.ThreeColor.Supplement.path_terminal_algorithmexact-algorithmsgraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every fixed , there are one one-sided Monte Carlo finite program and constants deciding every valid terminal restricted four-coloring instance with its valid maximal star packings in a polynomial in encoded input size times
Here is the original order, , , and
The program never accepts no-instances, succeeds with probability at least on each yes-instance, and meets the charged worst-case bound on every tape. The program and polynomial constants may depend on only, before all instances and packings. This is the additional path-DP terminal alternative used by Theorem 1.4.
Differences from the source:
- encoding: terminal instances after the two maximal-star preprocessing steps → valid restricted instances with supplied valid inclusion-maximal star packings, all structural counts computed from them; reason: the explicit finite input includes the graph, restrictions and packings; its size is polynomial in the original vertex count
- encoding: one-sided Monte Carlo with a fixed positive input-independent success probability → one-sided acceptance probability at least 1/2 with the charged worst-case bound on all coin tapes; reason: independent constant repetition normalizes success; further charged polynomial amplification handles all subcalls without changing an exponential base
Preamble
import Mathlib import Definitions.Def_FasterExactColoring_ThreeColor_Supplement_TerminalBounds set_option autoImplicit false
Formal statement
namespace FasterExactColoring.ThreeColor.Supplement
theorem path_terminal_algorithm (ε : ℝ) (hε : 0 < ε) :
∃ (A : Program) (C : ℝ) (d : ℕ), 0 < C ∧
terminalSolver .rand A C d (fun P K => pathTerminalFactor P K ε) := by sorry
end FasterExactColoring.ThreeColor.Supplement
Source
Ryosuke Yamano, Tetsuo Shibuya, STOC 2027 submission #727 (October 2026), Lemma 5.6, p. 14 (PDF p. 16)