Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma

Andris Ambainis, Jevgēnijs Vihrovs

We study the structure of sets $S\subseteq \{0,1{\}}^n$ with small sensitivity. The well-known Simon's lemma says that any $S\subseteq \{0,1{\}}^n$ of sensitivity $s$ must be of size a…