Binary recovery candidates and guarded label attachment
DefinitionStableMSR_Recovery_Supplement_BinaryRecoveryalgorithmsclusteringcomputational-complexity
A candidate receives the binary dimensions and rational distance array. On stable inputs its labels recover the optimal partition. A guarded wrapper attaches the labels to a canonical complete input so that malformed input stays outside verification.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_BinaryVerifier
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery
/-- Binary scalar fields and the row-major rational distance table. -/
abbrev Input := ℕ × ℕ × List ℚ
def fieldsOf (I : RationalInput) : Input := (I.n,I.k,I.table)
def ofFields (a : Input) : RationalInput := ⟨a.1,a.2.1,a.2.2⟩
def parseFields (w : Bits) : Input :=
let v := BinaryVerifier.unpackData (BinaryVerifier.numbers w)
(v.1,v.2.1,v.2.2.1)
/-- A candidate procedure is constrained only on stable, valid instances.
The output labels are represented in point order. -/
def Recovers (f : Input → List ℕ) (γ : ℚ) : Prop :=
∀ I : RationalInput, I.Valid → ∀ O : Partition I.n, Stable I.dist I.k γ O →
(f (fieldsOf I)).length = I.n ∧ labelsPartition I.n I.k (f (fieldsOf I)) = O
/-- Reattach labels only to a complete canonical distance table. Distances
and labels are counted separately before their self-delimited codes are joined. -/
def attach (f : Input → List ℕ) (w : Bits) : Bits :=
let a := parseFields w
let I := ofFields a
let labels := f a
if I.table.length = I.n*I.n ∧ encodeInput I = w ∧ labels.length = I.n then
encodeSpecified ⟨I,labels⟩
else []
end StableMSR.Recovery.Supplement.BinaryRecovery
Source
S. Ravichandran and L. Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Theorem 1.1, Appendix A.5 (bit complexity), and Proposition C.4. https://arxiv.org/abs/2611.03547