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

DOI10.1007/978-3-319-17142-5_12zbMATH Open1352.05180arXiv1406.0073OpenAlexW3101072755MaRDI QIDQ2948459FDOQ2948459

Authors: Jevgēnijs Vihrovs, Andris Ambainis 

Publication date: 30 September 2015

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

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$.

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

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

Mathematics Subject Classification ID

Extremal set theory (05D05)

Cites Work

• On the degree of Boolean functions as real polynomials
• Sensitivity vs. block sensitivity of Boolean functions
• CREW PRAM<scp>s</scp> and Decision Trees
• Complexity measures and decision tree complexity: a survey.
• Quantum lower bounds by polynomials
• Sensitivity versus block sensitivity of Boolean functions
• Boolean functions with small spectral norm
• Title not available (Why is that?)
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• Sensitivity versus certificate complexity 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)