Sensitivity vs. block sensitivity (an average-case study)

DOI10.1016/0020-0190(96)00105-6zbMath0875.94140OpenAlexW2079828635MaRDI QIDQ671409

Juan-Miguel Gracia

Publication date: 27 February 1997

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

Full work available at URL: https://doi.org/10.1016/0020-0190(96)00105-6

zbMATH Keywords

Boolean functionsSensitivityHarmonic analysisBlock sensitivity

Mathematics Subject Classification ID

Related Items

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, Boolean nested canalizing functions: a comprehensive analysis, On the average sensitivity of the weighted sum function, The simplified weighted sum function and its average sensitivity, A NOTE ON THE POLYNOMIAL REPRESENTATION OF BOOLEAN FUNCTIONS OVER GF(2), Complexity measures and decision tree complexity: a survey.

Cites Work

• Sensitivity vs. block sensitivity of Boolean functions
• A tight ω(loglog n)-bound on the time for parallel RAM's to compute nondegenerated boolean functions
• CREW PRAM<scp>s</scp> and Decision Trees
• Unnamed Item