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

DOI10.1016/0020-0190(96)00105-6zbMATH Open0875.94140OpenAlexW2079828635MaRDI QIDQ671409FDOQ671409

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

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

Cited In (10)

• 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
• The simplified weighted sum function and its average sensitivity

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)