Parity bounds for actual linear-sampler affine calls #
At a fixed second summand, one honest sampler value outside the actual bad-seed set bounds the complete component parity by twice the requested statistical error. This is the linearity step of Chattopadhyay--Liao, Extractors for Sum of Two Sources, Lemma 5.4, equation (5): https://arxiv.org/abs/2110.12652.
The sampler's linearity is explicit. No statistical guarantee or polynomial-time implementation of a sampler is asserted here.
theorem
Algebraic.Cutwidth.Extractor.affineLeakage_linear_parity_le
{n d t : ℕ}
{Out : Type u_1}
[Fintype Out]
(cb : (Fin n → Bool) → (Fin d → Bool) → List Bool → Out)
(p : (Fin n → Bool) → ℝ)
(sampler : (Fin n → Bool) → Option (Fin t) → Fin d → Bool)
(advice : Option (Fin t) → List Bool)
(linear : ∀ (x y : Fin n → Bool) (i : Option (Fin t)), sampler (xorInput x y) i = xorInput (sampler x i) (sampler y i))
(bit : Out → Bool)
(balanced : mapWeight bit (uniformWeight Out) = uniformWeight Bool)
(γ : ℝ)
(b : Fin n → Bool)
(good : sampler b none ∉ affineLeakageBadSeeds cb p sampler advice γ)
:
One escaping honest seed controls the actual full component parity after fixing a summand.