Proof of Claim B.1.2, p. A:45 — at most an fraction of -subsets overestimate a Boolean average by
ProvedObfImpossibility.PseudoOracle.chernoff_count_Tconcentrationcountingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sampling-without-replacement
There is an absolute constant with the following property. Let be a finite set, , and . Then the number of -element subsets with
is at most .
This is the Chernoff bound for sampling without replacement that the paper invokes ("most large subsets are good approximators of the average of a Boolean function"). Applied with , , and , it says that at most an fraction of the possible images satisfy inequality (9), which is the saving in the description of .
Formalization Note The constant is quantified before the type lives in, so it is universal. For the empty set has average and the count is ; for both sides are .
Preamble
import Mathlib import Definitions.Def_ObfImpossibility_PseudoOracle_Setting
Formal statement
namespace ObfImpossibility.PseudoOracle
/-- The Chernoff count, p. A:45 (proof of Claim B.1.2): there is an absolute constant
`c > 0` such that for every Boolean function `f` on a finite set `U`, every `m` and every
`ε > 0`, at most an `exp(-c m ε²)` fraction of the `m`-element subsets `T ⊆ U` satisfy
`Pr_{y∈T}[f(y) = 1] - Pr_{y∈U}[f(y) = 1] > ε`. -/
theorem chernoff_count_T :
∃ c : ℝ, 0 < c ∧ ∀ {α : Type} [DecidableEq α] (U : Finset α) (f : α → Bool) (m : ℕ)
(ε : ℝ), 0 < ε →
(((U.powersetCard m).filter fun T => ε < avg T f - avg U f).card : ℝ) ≤
Real.exp (-(c * (m : ℝ) * ε ^ 2)) * ((U.card.choose m : ℕ) : ℝ) := by sorry
end ObfImpossibility.PseudoOracle
Source
Barak et al., On the (Im)possibility of Obfuscating Programs, J. ACM 59(2) (2012), author's copy, p. A:45, Appendix B, proof of Claim B.1.2 (Chernoff bound for the sets T satisfying (9))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.