Sensitivity versus block sensitivity of Boolean functions

DOI10.1016/j.ipl.2011.02.001zbMath1260.68163arXiv1008.0521OpenAlexW1915875322MaRDI QIDQ1944916

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)

Related Items

Boolean nested canalizing functions: a comprehensive analysis, Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma, Minterm-transitive functions with asymptotically smallest block sensitivity, Sensitivity Versus Certificate Complexity of Boolean Functions, Tight bounds on sensitivity and block sensitivity of some classes of transitive functions, New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity, Induced subgraphs of hypercubes and a proof of the sensitivity conjecture

Cites Work

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