Theorem 3 — -approximation for uniform positive probabilities
OpenDataValidation.Supplement.theorem_3approximation-algorithmsdata-validationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1randomized-algorithms
For every fixed rational , there is a uniform encoded algorithm for every acyclic directed graph with valid encoded probabilities, , and on all edges. It returns a valid randomized adaptive policy satisfying
whenever , and runs in steps. The algorithmic output includes the paper's uniform random selection of an edge and the subsequent edge-optimal policy.
If , both the optimum and returned reward are zero; this case is stated with factor rather than excluded.
Differences from the source:
- encoding: is an arbitrary real probability → is rational; reason: the published DVP instance encoding uses rational probabilities, and every encoded instance of the theorem has such a fixed
- encoding: an -approximation when is left implicit → the empty-edge branch uses factor and has optimum zero; reason: avoids division by zero without adding
- encoding: running time is informal → there is an absolute natural constant and at most Cook–Levin steps; reason: the additive one totalizes the asymptotic bound at an empty input
- generalization: DVP instances have a transitive DAG by the model definition → Lean allows every acyclic directed graph satisfying the same probability and encoding conditions; reason: the paragraph following Theorem 4 explicitly says the approximation algorithms do not require transitivity, and every DVP instance specializes to this domain
Preamble
import Mathlib import Definitions.Def_DataValidation_Supplement_Algorithms set_option autoImplicit false
Formal statement
namespace DataValidation.Supplement
/-- **Theorem 3** (Tinguely--van der Heijden, *Approximation and Hardness for the Data
Validation Problem*, arXiv:2611.06773, sha256 6595f819..., p.2 (PDF p.3), proof p.9
(PDF p.10)). For every fixed rational `p ∈ (0,1]`, on arbitrary DAG instances with valid encoded
probabilities, unit probing costs and success probability `p` on every edge, a uniform encoded
algorithm returns a valid randomized adaptive policy whose reward is an `m`-approximation, in
`O(m n min{m,T})` Cook--Levin steps.
**Formalization Note.** Rational probabilities are the published instance encoding. The algorithm
may depend on the fixed `p`. Its finite policy family implements the paper's uniform random choice
of an edge followed by an edge-optimal policy. On the empty-edge instance, both optimum and reward
are zero; `max 1 m` states that harmless branch without adding `m > 0`. The additive `+1` in the
step bound is the standard totalization of big-O at zero. `IsDAGValid` omits only
transitivity from the base instance predicate, implementing the paper's explicit remark that these
algorithms work for arbitrary DAGs. -/
theorem theorem_3 (p : ℚ) (hp0 : 0 < p) (hp1 : p ≤ 1) :
∃ (A : PolicyAlgorithm) (C : ℕ), 0 < C ∧
IsPolicyApproximationOn A (fun I => max 1 I.E.card)
(fun I => IsDAGValid I ∧ IsUniform p I) ∧
∀ I, IsDAGValid I → 0 < I.T → IsUniform p I →
A.time I ≤ C * (I.E.card * I.n * min I.E.card I.T + 1) := by sorry
end DataValidation.Supplement
Source
Tinguely, van der Heijden, Approximation and Hardness for the Data Validation Problem, arXiv:2611.06773 (sha256 6595f819…), Theorem 3, p.2 and proof, p.9 (PDF pp.3, 10)