Proof of Theorem 5.16(2), p. 30 — ⟨c⁰_{r,a}, c⁰_{r′,a}⟩ = 1/2 if r = r′ and 0 otherwise
ProvedPrivLearn.MaskedParity.orthogonalityfourier-analysisp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1paritystatistical-query-learning
Let be a power of two and let examples be uniform on the MASKED-PARITY domain . For and ,
So is an orthonormal set for each , the Fourier fact behind the lower bound.
Formalization Note. is the restriction of to the half (zero on ). follows from .
Preamble
import Mathlib import Definitions.Def_PrivLearn_MaskedParity_Model import Definitions.Def_PrivLearn_MaskedParity_Oracle
Formal statement
namespace PrivLearn.MaskedParity
/-- **Orthogonality display** (p. 30). Let `d` be a power of two. For `r, r′ ∈ {0,1}^d` and
`a ∈ {0,1}`, `⟨c^0_{r,a}, c^0_{r′,a}⟩ = 1/2` if `r = r′` and `0` if `r ≠ r′`. -/
theorem orthogonality {d : ℕ} (hd : ∃ m : ℕ, d = 2 ^ m) (r r' : Fin d → ZMod 2) (a : ZMod 2) :
ip (half 0 (cMP r a)) (half 0 (cMP r' a)) = if r = r' then 1 / 2 else 0 := by sorry
end PrivLearn.MaskedParity
Source
Kasiviswanathan, Lee, Nissim, Raskhodnikova and Smith, What Can We Learn Privately?, arXiv:0803.0924v3, p. 30, proof of Theorem 5.16 part (2), display after the extension of c^0_{r,a}
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.