Sensitivity versus block sensitivity of Boolean functions

DOI10.1016/J.IPL.2011.02.001MaRDI QIDQ1944916zbMATH OpenOpenAlexFDO

Authors Madars Virza

Publication date 28 March 2013

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

sensitivitycomputational complexitycombinatorial problemsblock sensitivity

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: Determining the maximal separation between sensitivity and block sensitivity of Boolean functions is of interest for computational complexity theory. We construct a sequence of Boolean functions with bs(f) = 1/2 s(f)^2 + 1/2 s(f). The best known separation previously was bs(f) = 1/2 s(f)^2 due to Rubinstein. We also report results of computer search for functions with at most 12 variables.

Recommendations

• Sensitivity vs. block sensitivity of Boolean functions
• On block sensitivity and fractional block sensitivity
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• On the sensitivity conjecture
• Sensitivities and block sensitivities of elementary symmetric Boolean functions

Cites work

• CREW PRAM<scp>s</scp> and Decision Trees
• Complexity measures and decision tree complexity: a survey.
• Sensitivity vs. block sensitivity of Boolean functions
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions

Cited in

(15)

• scientific article; zbMATH DE number 6850428 (Why is no real title available?)
• On block sensitivity and fractional block sensitivity
• Size of sets with small sensitivity: a generalization of Simon's lemma
• Boolean functions with low average sensitivity depend on few coordinates
• Sensitivity versus certificate complexity of Boolean functions
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• A note on the polynomial representation of Boolean functions over \(\mathrm{GF}(2)\)
• Sensitivity vs. block sensitivity of Boolean functions
• Minterm-transitive functions with asymptotically smallest block sensitivity
• New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity
• Theory and Applications of Models of Computation
• Tight bounds on sensitivity and block sensitivity of some classes of transitive functions
• Properties and applications of Boolean function composition
• Boolean nested canalizing functions: a comprehensive analysis

This page was built for publication: Sensitivity versus block sensitivity of Boolean functions

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