Algorithm 1: the main loop
ProvedDirKECC1549.Asm.a1Loop_specalgorithm-implementationdirected-graphsedge-connectivityprogram-verificationword-ram
From the machine state of Algorithm 1 before vertex 0, a1Loop processes all vertices and ends in the state for , within ticks.
Context. This lemma belongs to the machine-checked word-RAM implementation of Lemma 1 (p.11): Algorithm 1 refining by small -out sets, with the deterministic local search of [GKK+26, Proposition 6] (FindOutPaths and recursive path reversals). The program is written in the structured language Stmt compiled to the published word-RAM; Run E s mem Q states that the statement s, started on mem, reaches its end in a state satisfying Q t mem' within t ticks. The input cells double as registers; they are saved at SV and read through the image ImgAt. All definitions are in the Definitions.Def_DirKECC1549_Impl_* modules.
Preamble
import Definitions.Def_DirKECC1549_Impl_L1Alg8
set_option autoImplicit false
open WordRAM Classical Finset
open DirKECC1549.Main DirKECC1549.Main.CostAux
open DirKECC1549 DirKECC1549.Asm
variable {w : Width} {n m : ℕ}Formal statement
theorem DirKECC1549.Asm.a1Loop_spec (E : Env) (orig : Memory w) (hm : 0 < m) (P : LP) (OR PR IR HR TR : ℕ)
(G : Fin m → Fin n × Fin n) (σ τ : Equiv.Perm (Fin m)) (K Δ FR W k : ℕ)
(hst : AlgStat P OR PR IR HR TR orig G σ τ) (hL : LsLay P n m K Δ FR W w.bits)
(hE : EnvOK E lsBody) (hs : ∀ x ∈ E.sites, x < 2 ^ w.bits) (hk : K = k - 1) (hk2 : 2 ≤ k)
(L0 : Fin n → ℕ) (hlab : ∀ u v : Fin n, L0 u = L0 v ↔ KEdgeConnected K G u v)
(GIb FRb OUTb : ℕ) (hlay : ALay P n m FR GIb FRb OUTb) (mm : Memory w)
(hS : AState P OR PR IR HR TR FR K Δ W orig k G L0 GIb FRb OUTb 0 mm) (h66 : (mm (P.SV + 66)).toNat = 0) :
Run E a1Loop mm (fun t mm' => AState P OR PR IR HR TR FR K Δ W orig k G L0 GIb FRb OUTb n mm' ∧
t ≤ n * (4 * lsTT K Δ E.sites.length K + 12 * (Δ + 1) + 433) + 9) := by sorrySource
Loukas Georgiadis, Evangelos Kipouridis, Evangelos Kosinas, Charis Papadopoulos, Christos Pergaminelis, STOC 2027 submission #1549 (October 2026), Section 3.1, Lemma 1 and Algorithm 1 (pp.10–12), using Proposition 6 of [GKK+26] (deterministic local search); word-RAM model of Hagerup (p.25). Implementation-level lemma of the verified program for Lemma 1.