Exact-zero OLS sample-deletion decision language
DefinitionSampleRemoval_Supplement_exactZeroDeletionLangleast-squaresoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1robustness-auditsample-removal
An instance is a finite list of observations with and , together with a deletion budget . It is a yes-instance exactly when some retained subset deletes at most observations, has a nonsingular intercept-plus-binary-regressor design, and has OLS slope exactly zero.
The language uses a canonical self-delimiting binary encoding of the observation list, signed integer responses, and the budget. It is the decision problem whose NP-hardness is asserted by Theorem 3.7.
Formalization Note Malformed strings are no-instances. Nonsingularity is positive definiteness of the retained Gram matrix, excluding the total-inverse junk value on singular designs.
Definition code
import Mathlib
import Definitions.Def_BinaryNat_Encoding
import Definitions.Def_CookLevin_Complexity
import Definitions.Def_SampleRemoval_gram
import Definitions.Def_SampleRemoval_ols
import Definitions.Def_SampleRemoval_ind
set_option autoImplicit false
open Matrix
namespace SampleRemoval.Supplement
/-- The exact-zero deletion decision language of Theorem 3.7, with a canonical binary encoding
of the finite list of observations and the deletion budget (Xu, Gao, Hu, *Rounding, Ranges, and
Exact Sample-Removal Audits for Least Squares*, STOC 2027 submission, manuscript sha256
`dcd33ace…`, Theorem 3.7, p.6 (PDF p.8)).
**Formalization Note** An observation is a pair `(xᵢ,yᵢ) : Bool × ℤ`; `false` and `true`
encode `xᵢ=0` and `xᵢ=1`. The list length and budget use `NPBinary.encodeNat`; an integer is
encoded by its sign bit followed by its encoded absolute value. Membership asks for a retained
set deleting at most `k` observations, a positive-definite intercept-plus-regressor Gram matrix,
and exactly zero second OLS coefficient. Thus malformed strings are no-instances and singular
retained designs are explicitly excluded. -/
def exactZeroDeletionLang : CookLevin.Language := fun code =>
∃ (data : List (Bool × ℤ)) (k : ℕ),
code = NPBinary.encodeNat data.length ++
data.flatMap (fun q => q.1 :: decide (q.2 < 0) :: NPBinary.encodeNat q.2.natAbs) ++
NPBinary.encodeNat k ∧
∃ S : Finset (Fin data.length),
data.length - S.card ≤ k ∧
let x : Fin data.length → Fin 2 → ℝ := fun i j =>
if j.1 = 0 then 1 else if (data.get i).1 then 1 else 0
let y : Fin data.length → ℝ := fun i => (data.get i).2
(SampleRemoval.gram x (SampleRemoval.ind S)).PosDef ∧
SampleRemoval.ols x y (SampleRemoval.ind S) ⟨1, by omega⟩ = 0
end SampleRemoval.Supplement
Source
Xu, Gao, Hu, Rounding, Ranges, and Exact Sample-Removal Audits for Least Squares, STOC 2027 submission (manuscript sha256 dcd33acebc1ccdc626c7ee41bfabc29795abe2e1cd9267d8cbd66d98f81c4b26), Theorem 3.7, p.6 (PDF p.8)