Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Explicit binary CNF-to-MSR distance table

Definition
StableMSR_Recovery_Supplement_SATMetric

by lreyzin · Nov 19, 2026 · Mathlib 0df444a (Lean v4.33.1)

algorithmsclusteringcomputational-complexity

An explicit integer distance table for the Gibson literal and private-point reduction on general CNF formulas, together with a binary-to-binary map on every string. Variable occurrences are compactly renamed before assigning exponentially separated radii. The table is given entrywise, so all its outputs can be computed without a graph shortest-path procedure.

Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_BinaryVerifier
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.SATMetric

/-- Literal, private, and clause vertices of the SAT reduction. The natural coordinates
are bounded by the formula dimensions when used in the distance table. -/
inductive Vertex
  | lit (i : ℕ) (s : Bool)
  | mark (i a : ℕ)
  | clause (c : ℕ)
deriving DecidableEq

abbrev Entry := ℕ × ℕ × ℕ
def repr : Vertex → Entry
  | .lit i b => (0,i,b.toNat)
  | .mark i a => (1,i,a)
  | .clause c => (2,c,0)

def entry (k t : ℕ) : Entry :=
  let w := k+3
  let i := t/w
  let j := t%w
  if t < k*w then if j < 2 then (0,i,j) else (1,i,j-2) else (2,t-k*w,0)

def weight (i : ℕ) := 2^i
def tableDist (h : ℕ → ℕ) (hit : ℕ → Bool → ℕ → Bool) (a b : Entry) : ℕ :=
  let i := a.2.1
  let j := b.2.1
  let u := a.2.2
  let v := b.2.2
  if a.1 = 0 then
    if b.1 = 0 then if i = j then (if u = v then 0 else h i) else h i+h j
    else if b.1 = 1 then (if i = j then h i else h i+2*h j)
    else h i + (if hit i (u==1) j then 0 else 1)
  else if a.1 = 1 then
    if b.1 = 0 then (if i = j then h j else h j+2*h i)
    else if b.1 = 1 then (if i = j then (if u = v then 0 else 2*h i) else 2*h i+2*h j)
    else 2*h i
  else if b.1 = 0 then h j + (if hit j (v==1) i then 0 else 1)
    else if b.1 = 1 then 2*h j else if i=j then 0 else 1

def D (hit : ℕ → Bool → ℕ → Bool) (x y : Vertex) : ℕ := tableDist weight hit (repr x) (repr y)

/-- Uncentered private points force a ball for every variable at its own scale. -/
def Admissible (k m : ℕ) : Vertex → Prop
  | .lit i _ => i < k
  | .mark i a => i < k ∧ a < k+1
  | .clause c => c < m

def BallCover (k m : ℕ) (hit : ℕ → Bool → ℕ → Bool) : Prop :=
  ∃ (v : Fin k → Vertex) (r : Fin k → ℝ),
    (∀ b, Admissible k m (v b)) ∧ (∀ b, 0 ≤ r b) ∧
    (∀ x, Admissible k m x → ∃ b, (D hit (v b) x : ℝ) ≤ r b) ∧
    ∑ b, r b ≤ ∑ i : Fin k, (weight i.val : ℝ)

def names (F : PvsNP.CNF) : List ℕ := (F.flatMap id).map Prod.snd
def slots (F : PvsNP.CNF) : List ℕ := 0 :: names F
def hit (F : PvsNP.CNF) (i : ℕ) (s : Bool) (c : ℕ) : Bool :=
  (F[c]?.getD []).any (fun l => (l.1 == s) && decide ((names F).idxOf l.2 = i))

/-- Every index passed to the power-of-two computation is capped by a physical input list. -/
def height (F : PvsNP.CNF) (i : ℕ) : ℕ :=
  BinaryVerifier.digits ((((slots F).take i).map (fun _ => false)) ++ [true])
def ids (F : PvsNP.CNF) : List ℕ :=
  let s := slots F
  List.range (((s.flatMap (fun _ => s ++ [0,0,0])) ++ F.map (fun _ => 0)).length)
def instanceOf (F : PvsNP.CNF) : ThresholdInput :=
  let k := (slots F).length
  let xs := ids F
  let n := xs.length
  let table := (List.range ((xs.flatMap (fun _ => xs)).length)).map fun t =>
    (tableDist (height F) (hit F) (entry k (t/n)) (entry k (t%n)) : ℚ)
  ⟨⟨n,k,table⟩,((height F k - 1 : ℕ) : ℚ)⟩

/-- A two-bit token either contributes data bits or ends the current field. -/
def scan (op : Bool → Bool → Option Bits) : Bits → Bits × List Bits
  | [] | [_] => ([],[])
  | a :: b :: w =>
    let r := scan op w
    match op a b with
    | none => ([],r.1::r.2)
    | some u => (u ++ r.1,r.2)

def chunks (op : Bool → Bool → Option Bits) (w : Bits) : List Bits :=
  let r := scan op w
  (r.1 :: r.2).dropLast
def clauseToken (a b : Bool) : Option Bits := if a && b then none else some [a,b]
def literalToken (a b : Bool) : Option Bits := if a then none else some [b]
def readLiteral (w : Bits) : PvsNP.Literal := (w.head?.getD false,BinaryVerifier.digits w.tail)
def parse (w : Bits) : PvsNP.CNF :=
  (chunks clauseToken w).map fun c => (chunks literalToken c).map readLiteral

/-- The binary reduction uses the empty, malformed threshold word outside canonical CNF codes. -/
def reduce (w : Bits) : Bits :=
  let F := parse w
  if PvsNP.encodeCNF F == w then encodeThreshold (instanceOf F) else []
end StableMSR.Recovery.Supplement.SATMetric
Source
Gibson, Kanade, Krohn, Pirwani, and Varadarajan, On Metric Clustering to Minimize the Sum of Radii, Algorithmica 57 (2010), Section 3, Theorem 2. https://www.cs.utsa.edu/~gibson/MetricKClustering.pdf . Ravichandran and Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Appendix C, https://arxiv.org/abs/2611.03547 . The explicit table used here adapts the literal and private-point construction to unrestricted finite metrics.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me