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

DOI10.1016/0020-0190(96)00105-6MaRDI QIDQ671409zbMATH OpenOpenAlexFDO

Authors 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 functionsHarmonic analysisSensitivityBlock sensitivity

Mathematics Subject Classification ID

Cites work

• scientific article; zbMATH DE number 3889430 (Why is no real title available?)
• 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
• Sensitivity vs. block sensitivity of Boolean functions

Cited in

(10)

• The simplified weighted sum function and its average sensitivity
• On block sensitivity and fractional block sensitivity
• Pseudo-average block sensitivity equals average sensitivity
• Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
• Computing Boolean functions from multiple faulty copies of input bits
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• A note on the polynomial representation of Boolean functions over \(\mathrm{GF}(2)\)
• Complexity measures and decision tree complexity: a survey.
• Boolean nested canalizing functions: a comprehensive analysis
• On the average sensitivity of the weighted sum function

This page was built for publication: Sensitivity vs. block sensitivity (an average-case study)

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