Theorem 2 — DVP/DkS approximation reduction and conditional hardness (corrected: exact reduction budget)
OpenDataValidation.Supplement.theorem_2approximation-hardnessdata-validationdensest-k-subgraphp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be any approximation factor. Every uniform -approximation algorithm for DVP on instances with and yields a uniform Densest -Subgraph approximation algorithm with factor
using , , and . The cases and are solved directly.
Consequently, on the same unit instances:
- under the cited Almost-ETH DkS hardness proposition, for every there is no polynomial-time -approximation algorithm for DVP;
- under the cited SPCH DkS hardness proposition, no approximation factor is achievable in time for any function .
The hardness hypotheses are explicit propositions about encoded DkS algorithms; the theorem asserts their implications rather than treating the cited propositions as results proved by this paper.
Differences from the source:
- correction: the parenthetical claims on every DkS instance → Lean states the exact , construction; reason: if while grows, then and but
- encoding: → the proof's exact factor for , with direct small cases; reason: this is the full constant proved on p.5
- encoding: algorithms and polynomial/FPT time are informal → uniform multi-tape Cook–Levin machines returning encoded feasible outputs with explicit step bounds; reason: fixes a concrete computation model without changing the instances
- encoding: Almost-ETH and SPCH are named hypotheses → the two DkS inapproximability consequences cited in Proposition 6 are explicit assumptions; reason: this paper imports rather than proves them
Preamble
import Mathlib import Definitions.Def_DataValidation_Supplement_DkS set_option autoImplicit false open Filter Topology
Formal statement
namespace DataValidation.Supplement
/-- **Theorem 2** (Tinguely--van der Heijden, *Approximation and Hardness for the Data
Validation Problem*, arXiv:2611.06773, sha256 6595f819..., p.2 (PDF p.3), proof pp.5--6
(PDF pp.6--7)), with the false parenthetical `T = Θ(opt)` minimally corrected.
1. Every factor-`α(T,m,n)` algorithm for DVP on unit instances yields a Densest `k`-Subgraph
algorithm with factor `α(T,m,n) * (4 + 2/(k-1))`, using exactly
`D = ceil(m*/k)` and `T = kD + m*`; the zero-optimum and `k < 2` cases are handled trivially.
2. The cited Almost-ETH consequence rules out polynomial-time
`2^{(log n)^{1-δ}}`-approximation for every `δ > 0`.
3. The cited SPCH consequence rules out every `a(T)=o(sqrt T)` approximation in
`g(T)n^{O(1)}` time, for every `g`.
**Formalization Note.** Algorithms are uniform Cook--Levin machines returning encoded finite
randomized policies. `AlmostETHDkSHardness` and `SPCHDkSHardness` explicitly state the two DkS
results imported as assumptions from Proposition 6; this theorem does not claim to prove those
hypotheses. The printed `T = Θ(opt)` is false: in a family with `m* = 1` and growing `k`, the
construction has `D = 1`, `T = k+1`, while `opt = 1`. The exact construction retained here is all
that the reduction uses; the clique-gap instances used in the two consequences still have the
needed parameter control. -/
theorem theorem_2 :
(∀ (α : ℕ → ℕ → ℕ → ℝ) (A : PolicyAlgorithm),
IsPolicyApproximation A (fun I => α I.T I.E.card I.n) Instance.IsUnit →
∃ B : DkSAlgorithm, IsDkSApproxFrom A α B) ∧
(AlmostETHDkSHardness →
∀ δ : ℝ, 0 < δ → ¬ ∃ A : PolicyAlgorithm, IsAlmostETHForbiddenDVP δ A) ∧
(SPCHDkSHardness →
∀ a : ℕ → ℝ, (∀ T, 1 ≤ a T) →
Tendsto (fun T : ℕ => a T / Real.sqrt T) atTop (nhds 0) →
∀ g : ℕ → ℕ, ¬ ∃ A : PolicyAlgorithm, IsSPCHForbiddenDVP a g A) := by sorry
end DataValidation.Supplement
Source
Tinguely, van der Heijden, Approximation and Hardness for the Data Validation Problem, arXiv:2611.06773 (sha256 6595f819…), Theorem 2, p.2, Proposition 6 and proof of Theorem 2, pp.4–6 (PDF pp.3, 5–7)