Sensitivity vs. block sensitivity of Boolean functions
From MaRDI portal
Publication:1894709
DOI10.1007/BF01200762zbMath0837.68080OpenAlexW2079009446MaRDI QIDQ1894709
Publication date: 16 April 1996
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01200762
Related Items (23)
Pseudo-average block sensitivity equals average sensitivity ⋮ Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables ⋮ Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions ⋮ Computing Boolean functions from multiple faulty copies of input bits ⋮ Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma ⋮ On the average sensitivity of the weighted sum function ⋮ Optimal embeddings of the exchanged hypercube and the dual-cube as vertex-induced subgraphs of the hypercube ⋮ Sensitivity versus block sensitivity of Boolean functions ⋮ On the resolution of the sensitivity conjecture ⋮ Unnamed Item ⋮ Conflict complexity is lower bounded by block sensitivity ⋮ Sensitivity vs. block sensitivity (an average-case study) ⋮ Sensitivity Versus Certificate Complexity of Boolean Functions ⋮ Maximal sensitivity of Boolean nested canalizing functions ⋮ The simplified weighted sum function and its average sensitivity ⋮ Sensitivity, affine transforms and quantum communication complexity ⋮ Sensitivities and block sensitivities of elementary symmetric 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 ⋮ Certificate complexity of elementary symmetric Boolean functions ⋮ Induced subgraphs of hypercubes and a proof of the sensitivity conjecture ⋮ Complexity measures and decision tree complexity: a survey. ⋮ Certificate complexity and symmetry of nested canalizing functions
Cites Work
This page was built for publication: Sensitivity vs. block sensitivity of Boolean functions
