Candidate-comparison count for the truncated min-plus dynamic program
DefinitionSampleRemoval_Supplement_dpWorkleast-squaresoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1robustness-auditsample-removal
For a truncation cap , the dynamic program examines when filling the entry for group and total . Its exact unit-cost comparison count is
This cost model makes the statement in Theorem 4.1 an explicit instance-independent bound.
Definition code
import Mathlib
import Definitions.Def_SampleRemoval_Supplement_FixedEffectsModel
set_option autoImplicit false
namespace SampleRemoval.Supplement
/-- The exact number of candidate comparisons in one truncated min-plus DP table through cap
`Kmax`: for group `g` and total `K`, candidates are `k=0,…,min(n_g,K)` (Xu, Gao, Hu, STOC
2027 submission, Theorem 4.1 proof, p.7 (PDF p.9)). -/
def dpWork {Γ : ℕ} (M : FixedEffectsModel Γ) (Kmax : ℕ) : ℕ :=
∑ g, ∑ K ∈ Finset.range (Kmax + 1), (min (M.nobs g) K + 1)
end SampleRemoval.Supplement
Source
Xu, Gao, Hu, Rounding, Ranges, and Exact Sample-Removal Audits for Least Squares, STOC 2027 submission (manuscript sha256 dcd33acebc1ccdc626c7ee41bfabc29795abe2e1cd9267d8cbd66d98f81c4b26), Section 4, p.7 (PDF p.9)