ECCC-Report TR14-077https://eccc.weizmann.ac.il/report/2014/077Comments and Revisions published for TR14-077en-usTue, 07 Jun 2016 14:00:30 +0300
Revision 2
| Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma |
Andris Ambainis,
Jevgenijs Vihrovs
https://eccc.weizmann.ac.il/report/2014/077#revision2We 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 parallel computing and the "sensitivity vs. block sensitivity" conjecture.
In this paper, we take a deeper look at the size of such sets and their structure. We show an unexpected "gap theorem": if $S\subseteq\{0, 1\}^n$ has sensitivity $s$, then we either have $|S|=2^{n-s}$ or $|S|\geq \frac{3}{2} 2^{n-s}$. This is shown via classifying such sets into sets that can be constructed from low-sensitivity subsets of $\{0, 1\}^{n'}$ for $n'<n$ and irreducible sets which cannot be constructed in such a way and then proving a lower bound on the size of irreducible sets.
This provides new insights into the structure of low sensitivity subsets of the Boolean hypercube $\{0, 1\}^n$.Tue, 07 Jun 2016 14:00:30 +0300https://eccc.weizmann.ac.il/report/2014/077#revision2
Revision 1
| Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma |
Andris Ambainis,
Jevgenijs Vihrovs
https://eccc.weizmann.ac.il/report/2014/077#revision1We 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 parallel computing and the "sensitivity vs. block sensitivity" conjecture.
In this paper, we take a deeper look at the size of such sets and their structure. We show an unexpected "gap theorem": if $S\subseteq\{0, 1\}^n$ has sensitivity $s$, then we either have $|S|=2^{n-s}$ or $|S|\geq \frac{3}{2} 2^{n-s}$. This is shown via classifying such sets into sets that can be constructed from low-sensitivity subsets of $\{0, 1\}^{n'}$ for $n'<n$ and irreducible sets which cannot be constructed in such a way and then proving a lower bound on the size of irreducible sets.
This provides new insights into the structure of low sensitivity subsets of the Boolean hypercube $\{0, 1\}^n$.Tue, 10 Jun 2014 19:11:01 +0300https://eccc.weizmann.ac.il/report/2014/077#revision1
Paper TR14-077
| Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma |
Andris Ambainis,
Jevgenijs Vihrovs
https://eccc.weizmann.ac.il/report/2014/077We 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 parallel computing and the "sensitivity vs. block sensitivity" conjecture.
In this paper, we take a deeper look at the size of such sets and their structure. We show an unexpected "gap theorem": if $S\subseteq\{0, 1\}^n$ has sensitivity $s$, then we either have $|S|=2^{n-s}$ or $|S|\geq \frac{3}{2} 2^{n-s}$. This is shown via classifying such sets into sets that can be constructed from low-sensitivity subsets of $\{0, 1\}^{n'}$ for $n'<n$ and irreducible sets which cannot be constructed in such a way and then proving a lower bound on the size of irreducible sets.
This provides new insights into the structure of low sensitivity subsets of the Boolean hypercube $\{0, 1\}^n$.Tue, 03 Jun 2014 12:15:19 +0300https://eccc.weizmann.ac.il/report/2014/077