Majority as the final sumset-extractor stage

Chattopadhyay and Liao, Extractors for Sum of Two Sources (2021), use majority after their reduction to non-oblivious bit-fixing sources in the proof of Theorem 2. This module gives that final deterministic operation, with ties returning false, and the signed vote margin on any designated set of good coordinates. It does not construct the preceding reduction.

def Algebraic.Cutwidth.Extractor.majorityEval (x : List Bool) : List Bool

Evaluate strict majority uniformly on an input of any length. The empty input and ties return the one-bit verdict false.

Equations

• Algebraic.Cutwidth.Extractor.majorityEval x = [Complexity.majority fun (i : Fin x.length) => x[i]]

def Algebraic.Cutwidth.Extractor.voteMargin {n : ℕ} (good : Finset (Fin n)) (x : Fin n → Bool) : ℤ

The number of true votes minus false votes on the designated good coordinates.

Equations

• Algebraic.Cutwidth.Extractor.voteMargin good x = 2 * ↑{i ∈ good | x i = true}.card - ↑good.card