Polynomial-size layered decoding of separator witnesses
DefinitionStableMSR_Recovery_Supplement_BlockPolicyDecoderalgorithmsclustering
Trace one component chain for each input label. Give each component at each depth one representative, output its bag and link it to the previous component. Unused slots carry empty bags attached to the root.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_ParentBagCertificates
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch
def blank : Rule := ([],[],[])
def startRow (z : GraphInput) (rs : List Rule) (x : ℕ) :=
((rs.filter (fun r=>r.1.contains x && contained z (border z r.1) [])).head?).getD blank
def descend (z : GraphInput) (rs : List Rule) (x : ℕ) (r : Rule) :=
if r.2.1.contains x then blank else
((rs.filter (fun q=>q.1.contains x && r.2.2.any (fun d=>same z q.1 d))).head?).getD blank
def traceRow (z : GraphInput) (rs : List Rule) (x d : ℕ) :=
(descend z rs x)^[(z.1.take d).length] (startRow z rs x)
def traceKeys (z : GraphInput) : List Key :=
zeroKey :: (List.range z.1.length).flatMap (fun d=>(List.range z.1.length).map (fun i=>(d+1,i)))
def anchor (z : GraphInput) (r : Rule) := z.1.findIdx (fun x=>r.1.contains x)
def slotRow (z : GraphInput) (rs : List Rule) (p : Key) :=
traceRow z rs (z.1[p.2]?.getD 0) (p.1-1)
def marked (z : GraphInput) (rs : List Rule) (p : Key) : Bool :=
let r := slotRow z rs p
decide (0<p.1) && r.1.contains (z.1[p.2]?.getD 0) && decide (anchor z r=p.2)
def traceBag (z : GraphInput) (rs : List Rule) (p : Key) :=
if marked z rs p then (slotRow z rs p).2.1 else []
def traceParent (z : GraphInput) (rs : List Rule) (p : Key) : Key :=
if decide (1<p.1) && marked z rs p then
(p.1-1,anchor z (traceRow z rs (z.1[p.2]?.getD 0) (p.1-2))) else zeroKey
def decodePolicy (a : GraphInput × List Rule) : FactorLayout :=
parentLayout (traceKeys a.1) (traceParent a.1 a.2) (traceBag a.1 a.2)
end StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch
Source
Binary layout construction from the tight-block search table.