Theory of Computing
-------------------
Title : A Communication Game Related to the Sensitivity Conjecture
Authors : Justin Gilmer, Michal Koucky, and Michael Saks
Volume : 13
Number : 7
Pages : 1-18
URL : http://www.theoryofcomputing.org/articles/v013a007
Abstract
--------
One of the major outstanding foundational problems about Boolean
functions is the _sensitivity conjecture_, which asserts that the
degree of a Boolean function is bounded above by some fixed power of
its sensitivity. We propose an attack on the sensitivity conjecture in
terms of a novel two-player communication game. A lower bound of the
form $n^{\Omega(1)}$ on the cost of this game would imply the
sensitivity conjecture.
To investigate the problem of bounding the cost of the game, three
natural (stronger) variants of the question are considered. For two of
these variants, protocols are presented that show that the hoped-for
lower bound does not hold. These protocols satisfy a certain
monotonicity property, and we show that the cost of any monotone
protocol satisfies a strong lower bound in the original variant.
There is an easy upper bound of $\sqrt{n}$ on the cost of the game. We
also improve slightly on this upper bound. This game and its
connection to the sensitivity conjecture was independently discovered
by Andy Drucker (arXiv:1706.07890).
A preliminary version of this paper appeared in the
Proceedings of the 6th Innovations in Theoretical
Computer Science conference, 2015.