Binary maps from exact MSR threshold decision to stability verification and recognition
DefinitionStableMSR_Recovery_Supplement_HubReductionFor a valid rational threshold instance, the maps construct the hub-and-dummy distance table in row-major order. The verification output includes label zero for the source and hub, and a distinct positive label for each dummy. The recognition output encodes the same instance without the labels. Invalid inputs map to a fixed one-point yes-instance, as the source language is complemented. The maps use rational arithmetic and finite tests for the metric axioms.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_Languages
import Mathlib.Logic.Equiv.Fin.Basic
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.HubReduction
/-- Check the rational source metric, the target cluster count, and the threshold. -/
def validData (T : ThresholdInput) : Bool :=
let I := T.input
decide (I.table.length = I.n * I.n ∧ 1 ≤ I.k ∧ I.k ≤ I.n ∧ 0 < T.threshold ∧
(∀ x y : Fin I.n, I.qdist x y = 0 ↔ x = y) ∧
(∀ x y : Fin I.n, I.qdist x y = I.qdist y x) ∧
(∀ x y z : Fin I.n, I.qdist x z ≤ I.qdist x y + I.qdist y z))
def sourceDiameter (I : RationalInput) : ℚ :=
let U := (Finset.univ : Finset (Fin I.n))
if h : U.Nonempty then U.sup' h (fun x => U.sup' h (I.qdist x)) else 0
/-- Flatten a rational distance table in the order used by RationalInput.qdist. -/
def tabulate (n k : ℕ) (q : Fin n → Fin n → ℚ) : RationalInput :=
⟨n,k,List.ofFn (fun i : Fin (n*n) =>
let xy : Fin n × Fin n := finProdFinEquiv.symm i
q xy.1 xy.2)⟩
/-- Source and hub have label 0. The k+1 dummies receive successive labels 1 through k+1. -/
def hubInstance (γ : ℚ) (T : ThresholdInput) : SpecifiedInput :=
let I := T.input
let n := I.n
let N := n + I.k + 2
let τ := T.threshold
let R := 1 + sourceDiameter I + τ + τ / (γ-1)
let δ := γ * R - τ
let L := δ + R + 1
let q (x y : Fin N) :=
if x = y then 0 else
if hx : x.val < n then
if hy : y.val < n then I.qdist ⟨x.val,hx⟩ ⟨y.val,hy⟩
else if y.val = n then R else L
else if y.val < n then
if x.val = n then R else L
else if x.val = n ∨ y.val = n then L else δ
⟨tabulate N (I.k+2) q, List.ofFn (fun x : Fin N => x.val - n)⟩
/-- A fixed yes-instance for strings outside the domain of valid threshold encodings. -/
def singletonInstance : SpecifiedInput := ⟨⟨1,1,[0]⟩,[0]⟩
def output (γ : ℚ) (w : Bits) : SpecifiedInput :=
match decodeThreshold w with
| some T => if validData T then hubInstance γ T else singletonInstance
| none => singletonInstance
def verificationMap (γ : ℚ) (w : Bits) : Bits := encodeSpecified (output γ w)
def recognitionMap (γ : ℚ) (w : Bits) : Bits := encodeInput (output γ w).input
end StableMSR.Recovery.Supplement.HubReduction
Source
Ravichandran and Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Theorem 5.1 and Appendix C, equations (3)–(5), pp. 24–25.