184 Communication Complexity — Dual Hard Sample

184.1 Overview

This module provides the sample-level half of the Alice/Bob symmetry used in the randomized lower bound for set disjointness (the “WLOG” step of [RY20, Thm. 6.13]): the involution CommunicationComplexity.Functions.Disjointness.RandomizedLowerBound.dualHardSample on hard samples, which swaps the two players’ roles and reverses the coordinate order, together with transport lemmas describing how bits, sets, special coordinates and windowed conditioning vectors of a hard sample behave under it. The declaration documented here is the shared engine behind the windowed-vector duality lemmas.

184.2 Declarations

Theorem 184.1 Windowed Alice bits of the dual sample are reversed Bob bits

✓

Let \(\omega \) be a hard sample on \(n\) coordinates with special coordinate \(T\), and let \(P, Q\) be decidable binary relations on \(\mathrm{Fin}\, n\) such that for every \(i\), \(P(i, \mathrm{rev}(T)) \iff Q(T, \mathrm{rev}(i))\), where \(\mathrm{rev}\) is the order-reversing bijection \(i \mapsto n-1-i\) on \(\mathrm{Fin}\, n\). Then the Boolean vector obtained from Alice’s bits of the dual sample CommunicationComplexity.Functions.Disjointness.RandomizedLowerBound.dualHardSample by keeping \(x_i\) exactly when \(P(i, \mathrm{rev}(T))\) holds (and setting the remaining coordinates to \(\mathtt{false}\)) equals the coordinate reversal of the vector obtained from Bob’s bits of the original sample \(\omega \) by keeping \(y_i\) exactly when \(Q(T, i)\) holds:

\[ \Bigl(i \mapsto [P(i,\mathrm{rev}\, T)]\cdot x_i(\omega ^{\mathrm{dual}})\Bigr) \; =\; \mathrm{reverse}\Bigl(i \mapsto [Q(T,i)]\cdot y_i(\omega )\Bigr). \]