Title: A Note on a Communication Game,
Abstract: We describe a communication game, and a conjecture about this game, whose
proof would imply the well-known Sensitivity Conjecture asserting a polynomial
relation between sensitivity and block sensitivity for Boolean functions. The
author defined this game and observed the connection in Dec. 2013 - Jan. 2014.
The game and connection were independently discovered by Gilmer, Koucký, and
Saks, who also established further results about the game (not proved by us)
and published their results in ITCS '15 [GKS15].
This note records our independent work, including some observations that did
not appear in [GKS15]. Namely, the main conjecture about this communication
game would imply not only the Sensitivity Conjecture, but also a stronger
hypothesis raised by Chung, Füredi, Graham, and Seymour [CFGS88]; and,
another related conjecture we pose about a "query-bounded" variant of our
communication game would suffice to answer a question of Aaronson, Ambainis,
Balodis, and Bavarian [AABB14] about the query complexity of the "Weak Parity"
problem---a question whose resolution was previously shown by [AABB14] to
follow from a proof of the Chung et al. hypothesis.