Documentation

Complexity.Computability.Communication.TopDown.Majority

Top-down lower bounds for majority #

The two Hamming layers on either side of the threshold of strict majority (strictMajority, which is false at a tie) have entropy deficit O(log n), and from every point at least half of the coordinates lead to the other layer by one flip. This gives bilateral density limits at rate 16 / n, so Korten's adversary applies, and the logarithmic initial deficit keeps the exponent 1 / (d - 1): no protocol with d messages of ε n ^ (1 / (d - 1)) bits solves the Karchmer–Wigderson game of strict majority on n bits for large n (strictMajority_communication_lower_bound). This extends the parity argument of Korten [Kor26].

Main definitions #

Main results #

References #

Hamming layers and the initial majority deficit #

Strict majority (strictMajority) is false at a tie, so the two layers at weights n / 2 and n / 2 + 1 straddle its threshold.

source
noncomputable def Cslib.Communication.strictMajorityDeficitBound (n : ℕ) :
ℝ

A common deficit and density-limit bound for the two majority boundary layers. The logarithmic term bounds their entropy deficit; 128 bounds the mask size.

Instances For

    Absorbing the logarithmic initial deficit #

    The middle-layer deficit bound is little-o of every positive power of n. Thus replacing the parity deficit 1 with this logarithmic bound preserves the exponent 1/(d-1) in a d-round communication lower bound.

    The two layers around the threshold of strict majority #

    The largest binomial coefficient is at least 2^n/(n+1), and its upper neighbor is at least half as large. This gives a logarithmic entropy deficit for both boundary layers, for even as well as odd input sizes.

    Density limits from many single-bit neighbors #

    At rate 16/n, a mask hits any set of at least n/2 coordinates with probability at least 8/9. Its expected size is 16, so the probability that it has more than 128 coordinates is at most 1/8. A selected single-bit neighbor then gives fiber density at least 2^(-128).

    Applying this to the two middle Hamming layers initializes Korten's top-down adversary for strict majority, extending his initialization for parity [Kor26].

    The communication lower bound for strict majority #

    The bilateral density adversary starts from the two layers around the threshold, and the power-law budget absorbs their logarithmic entropy deficit. This extends the argument of Korten [Kor26], whose Theorem 3 is the case of parity.

    source
    theorem Cslib.Communication.RoundProtocol.not_solvesKW_strictMajority {M : Type u_1} [Fintype M] {n d : ℕ} (P : KWRoundProtocol (Fin n) M (d + 1)) {m : ℝ} (hM : ↑(Fintype.card M) ≤ 2 ^ m) (hm : 0 ≤ m) (hsize : 64 * (32768 * 194 ^ d * (m + strictMajorityDeficitBound n)) ^ d ≤ ↑n) :
    ¬SolvesKW P (strictMajority n)

    The bound for strict majority with explicit constants: no protocol with d + 1 messages of at most m bits solves the Karchmer–Wigderson game of strict majority on n bits when 64 (32768 · 194 ^ d (m + strictMajorityDeficitBound n)) ^ d ≤ n.

    source
    theorem Cslib.Communication.strictMajority_communication_lower_bound (rounds : ℕ) (hrounds : 2 ≤ rounds) :
    ∃ (ε : ℝ), 0 < ε ∧ ∃ (N : ℕ), ∀ (n : ℕ), N ≤ n → ∀ {M : Type u} [inst : Fintype M], ↑(Fintype.card M) ≤ 2 ^ (ε * ↑n ^ (↑(rounds - 1))⁻¹) → ∀ (P : KWRoundProtocol (Fin n) M rounds), ¬RoundProtocol.SolvesKW P (strictMajority n)

    The communication lower bound for strict majority, extending Korten, Theorem 3: for every d ≥ 2 there is ε > 0 such that, for all large n, no protocol with d messages from an alphabet of at most 2 ^ (ε n ^ (1 / (d - 1))) letters solves the Karchmer–Wigderson game of strict majority on n bits.