Size of sets with small sensitivity: a generalization of Simon's lemma

DOI10.1007/978-3-319-17142-5_12MaRDI QIDQ2948459zbMATH OpenOpenAlexFDO

Authors Jevgēnijs Vihrovs, Andris Ambainis

Publication date 30 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.0073

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: We study the structure of sets $Ssubseteq{0,1}^n$ with small sensitivity. The well-known Simon's lemma says that any $Ssubseteq{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 $Ssubseteq{0,1}^n$ has sensitivity $s$, then we either have $|S|=2^{n-s}$ or $|S|geqfrac322^{n-s}$. This is shown via classifying such sets into sets that can be constructed from low-sensitivity subsets of ${0,1}^{n^{\prime }}$ for $n^{\prime }<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$.

Recommendations

• On the sensitivity conjecture
• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• On the sensitivity conjecture for disjunctive normal forms
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• scientific article; zbMATH DE number 6789278

Cites work

• scientific article; zbMATH DE number 3829252 (Why is no real title available?)
• Boolean functions with small spectral norm
• CREW PRAM<scp>s</scp> and Decision Trees
• Complexity measures and decision tree complexity: a survey.
• On the degree of Boolean functions as real polynomials
• Quantum lower bounds by polynomials
• Sensitivity versus block sensitivity of Boolean functions
• Sensitivity versus certificate complexity of Boolean functions
• Sensitivity vs. block sensitivity of Boolean functions
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• Tighter relations between sensitivity and other complexity measures

Cited in

(5)

• A tighter relation between sensitivity complexity and certificate complexity
• Sensitivity versus certificate complexity of Boolean functions
• Low-sensitivity functions from unambiguous certificates
• Does looking inside a circuit help?
• Tight bounds on sensitivity and block sensitivity of some classes of transitive functions

This page was built for publication: Size of sets with small sensitivity: a generalization of Simon's lemma

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2948459)