The layered witness decoder runs in polynomial bit time
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch.layered_decoder_bit_programalgorithmsclusteringdynamic-programming
Trace each label for at most the input-list length. The live state is one rule from the input or the empty rule. There are one plus n squared layout slots even on malformed tables.
Preamble
import Definitions.Def_QuantumMaxCutFiniteNumericRuntime import Definitions.Def_StableMSR_Recovery_Supplement_BlockPolicyDecoder open StableMSR.Recovery StableMSR.Recovery.Supplement.BinaryRecovery open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch open StableMSR.Recovery.DecompositionSearch RobertsonSeymour1986.GM5 open OAI.MetricKMedian.Binary.Automatic
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch.layered_decoder_bit_program : Poly decodePolicy := by sorry
Source
Constructive binary implementation of the tight-block recurrence in StableMSR.Recovery.DecompositionSearch.finite_decomposition_search, https://prove2.me/theorems/d4f2a14a-b18f-44f7-966a-d1411797cf17.