Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > INEQUALITIES ON BOOLEAN HYPERCUBE:
Reports tagged with Inequalities on Boolean Hypercube:
TR14-077 | 2nd June 2014
Andris Ambainis, Jevgenijs Vihrovs

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

Revisions: 2

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 at least $2^{n-s}$. This result has been useful for proving lower bounds on sensitivity of Boolean functions, with applications to the theory of ... more >>>




ISSN 1433-8092 | Imprint