While this submission is a draft, it cannot be used by other submissions.

Proof of `Depth and approximation loss of balanced recursion` (1st statement)

groundedproofs/Lax263307Proofs/RecursionDepth.lean · lax-263307

What this proof establishes

no assumptions

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

Bernoulli's inequality gives (1−δ)levels≥1−levels∗δ≥1−ε(1-δ)^levels ≥ 1-levels*δ ≥ 1-ε. The certified upper bound dominates every independent-set cardinality, so the returned set has the requested unweighted approximation guarantee.

Attribution

Bonnet–Chang, approximation guarantee in Theorem 15.