Explicit binary CNF-to-MSR distance table
DefinitionStableMSR_Recovery_Supplement_SATMetricalgorithmsclusteringcomputational-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.