Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions

DOI10.1016/j.ic.2002.12.001zbMath1072.68047OpenAlexW2116993798MaRDI QIDQ1887146

Samuel Kutin, Claire M. Kenyon

Publication date: 23 November 2004

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2002.12.001

zbMATH Keywords

sensitivityblock sensitivityBoolean function complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30)

Related Items

Alternation, sparsity and sensitivity: bounds and exponential gaps ⋮ Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma ⋮ Sensitivity versus block sensitivity of Boolean functions ⋮ Sensitivity Versus Certificate Complexity of Boolean Functions ⋮ An improved lower bound on the sensitivity complexity of graph properties ⋮ Maximal sensitivity of Boolean nested canalizing functions ⋮ Unnamed Item ⋮ A tighter relation between sensitivity complexity and certificate complexity ⋮ Sensitivities and block sensitivities of elementary symmetric Boolean functions ⋮ New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity ⋮ Certificate complexity of elementary symmetric Boolean functions ⋮ Induced subgraphs of hypercubes and a proof of the sensitivity conjecture ⋮ Certificate complexity and symmetry of nested canalizing functions

Cites Work

• Unnamed Item
• Unnamed Item
• Sensitivity vs. block sensitivity (an average-case study)
• The critical complexity of graph properties
• The equivalence of two problems on the cube
• On the degree of Boolean functions as real polynomials
• Sensitivity vs. block sensitivity of Boolean functions
• Sensitive functions and approximate problems
• Trade-Offs between Depth and Width in Parallel Computation
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• CREW PRAM<scp>s</scp> and Decision Trees