A total binary verifier for sum-of-radii instability
DefinitionStableMSR_Recovery_Supplement_BinaryVerifieralgorithmsclusteringcomputational-complexity
The algorithm reconstructs canonical candidate fields, validates the source metric and both labelings, checks the applicable perturbation inequalities, and compares the two exact sums of radii. It compares equality of partitions independently of the label names. Every iteration is bounded by the length of a decoded list, including on malformed inputs.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_Languages
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryVerifier
/-- The pending field and all subsequent fields, including the final unfinished field. -/
def fields : Bits → Bits × List Bits
| [] | [_] => ([],[])
| true :: b :: w => let r := fields w; (b :: r.1,r.2)
| false :: _ :: w => let r := fields w; ([],r.1 :: r.2)
def digits : Bits → ℕ
| [] => 0
| b :: w => b.toNat + 2*digits w
/-- The terminating field marker creates a trailing empty field. Canonical re-encoding
checks both delimiter bits and the normalized binary representation. -/
def numbers (w : Bits) : List ℕ :=
let r := fields w
((r.1 :: r.2).dropLast).map digits
abbrev Data := ℕ × ℕ × List ℚ × List ℕ
abbrev Witness := List ℚ × List ℕ
def numAt (ns : List ℕ) (i : ℕ) := ns[i]?.getD 0
def ratHead (ns : List ℕ) : ℚ :=
let a := (numAt ns 1 : ℚ)
(if numAt ns 0 = 0 then a else -a) / (numAt ns 2 : ℚ)
def triples (ns : List ℕ) : List ℚ :=
((List.range ns.length).take (ns.length/3)).map (fun i => ratHead (ns.drop (3*i)))
def unpackWitness (n : ℕ) (ns : List ℕ) : Witness :=
(triples (ns.take (3*(n*n))), ns.drop (3*(n*n)))
def unpackData (ns : List ℕ) : Data :=
let n := numAt ns 0
(n,numAt ns 1,unpackWitness n (ns.drop 2))
def dataFields (v : Data) : List ℕ := [v.1,v.2.1] ++ v.2.2.1.flatMap ratNumbers ++ v.2.2.2
def witnessFields (W : Witness) : List ℕ := W.1.flatMap ratNumbers ++ W.2
def specified (v : Data) : SpecifiedInput := ⟨⟨v.1,v.2.1,v.2.2.1⟩,v.2.2.2⟩
def witness (W : Witness) : RationalWitness := ⟨W.1,W.2⟩
/-- The outer loop is always bounded by the length of the decoded list, even if $k$ is malformed. -/
def classes (k : ℕ) (lab : List ℕ) : List ℕ := (List.range lab.length).take k
def members (lab : List ℕ) (j : ℕ) : List ℕ :=
(List.range lab.length).filter (fun i => decide (numAt lab i = j))
def labelsOK (k : ℕ) (lab : List ℕ) : Bool :=
lab.all (fun j => decide (j < k)) && (classes k lab).all (fun j => !(members lab j).isEmpty)
def distAt (n : ℕ) (ds : List ℚ) (i j : ℕ) : ℚ := ds[i*n+j]?.getD 0
def triangle (n : ℕ) (ds : List ℚ) (pts : List ℕ) : Bool :=
pts.all fun i => pts.all fun j => pts.all fun l =>
decide (distAt n ds i l ≤ distAt n ds i j + distAt n ds j l)
def metricOK (n : ℕ) (ds : List ℚ) (pts : List ℕ) : Bool :=
(pts.all fun i => pts.all fun j =>
((decide (distAt n ds i j = 0)) == (decide (i = j))) &&
decide (distAt n ds i j = distAt n ds j i)) && triangle n ds pts
def valid (v : Data) : Bool :=
decide (v.2.2.1.length = v.1*v.1) && decide (1 ≤ v.2.1) && decide (v.2.1 ≤ v.1) &&
decide (v.2.2.2.length = v.1) && labelsOK v.2.1 v.2.2.2 &&
metricOK v.1 v.2.2.1 (List.range v.2.2.2.length)
def perturbOK (metric : Bool) (γ : ℚ) (n : ℕ) (ds ps : List ℚ) (pts : List ℕ) : Bool :=
(pts.all fun i => pts.all fun j =>
decide (distAt n ps i j = distAt n ps j i) && decide (distAt n ds i j ≤ distAt n ps i j) &&
decide (distAt n ps i j ≤ γ*distAt n ds i j)) && (!metric || triangle n ps pts)
def samePartition (a b : List ℕ) : Bool :=
(List.range a.length).all fun i => (List.range a.length).all fun j =>
(decide (numAt a i = numAt a j)) == (decide (numAt b i = numAt b j))
def hi (xs : List ℚ) := xs.max?.getD 0
def lo (xs : List ℚ) := xs.min?.getD 0
def blockRadius (n : ℕ) (ds : List ℚ) (C : List ℕ) : ℚ :=
lo (C.map fun c => hi (C.map fun i => distAt n ds c i))
def total (n k : ℕ) (ds : List ℚ) (lab : List ℕ) : ℚ :=
((classes k lab).map fun j => blockRadius n ds (members lab j)).sum
def competitive (metric : Bool) (γ : ℚ) (v : Data) (w : Witness) : Bool :=
decide (w.1.length = v.1*v.1) && decide (w.2.length = v.1) && labelsOK v.2.1 w.2 &&
perturbOK metric γ v.1 v.2.2.1 w.1 (List.range v.2.2.2.length) &&
!samePartition v.2.2.2 w.2 && decide (total v.1 v.2.1 w.1 w.2 ≤ total v.1 v.2.1 w.1 v.2.2.2)
/-- A total checker. Every synthesized input or witness is compared with its canonical encoding. -/
def check (metric : Bool) (xy : Bits × Bits) : Bool :=
let ns := numbers xy.1
let γ := ratHead ns
let v := unpackData (ns.drop 3)
let w := unpackWitness v.1 (numbers xy.2)
(packNats (ratNumbers γ ++ dataFields v) == xy.1) &&
(packNats (witnessFields w) == xy.2) && decide (1 ≤ γ) && valid v && competitive metric γ v w
/-- The input-side test used when specializing the uniform checker to a fixed factor. -/
def specifiedOK (raw : Bits) : Bool :=
let v := unpackData (numbers raw)
(packNats (dataFields v) == raw) && valid v
end StableMSR.Recovery.Supplement.BinaryVerifier
Source
Shyam Ravichandran and Lev Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Appendix C, Lemma C.3 and Theorem 5.1. https://arxiv.org/abs/2611.03547