Polynomial bit complexity of the executable cluster LP rounder
ProvedDualSepClusterLP.sparseRounderPolynomialTimeapproximation-algorithmscluster-lpcorrelation-clustering
A single Turing machine with a finite work alphabet evaluates the explicit Boolean word function for sparse clock and pivot rounding in time polynomial in the length of its input.
Preamble
import Definitions.Def_DualSepClusterLP_SparseRounder
Formal statement
namespace DualSepClusterLP
theorem sparseRounderPolynomialTime :
∃ (M : Turing.TM2ComputableAux Bool Bool) (A b : ℕ),
(∀ k, Finite (M.tm.Γ k)) ∧ ∀ (w : List Bool),
Nonempty (Turing.TM2OutputsInTime M.tm (w.map M.inputAlphabet.symm)
(some ((RoundWire.output w).map M.outputAlphabet.symm)) (A * (w.length + 1)^b)) := by sorry
end DualSepClusterLPSource
David García-Soriano and Antoine Schohn, Approximate Dual Separation for the Cluster LP, Appendix F (conditional-expectation rounding), https://arxiv.org/abs/2607.27829.