Sensitivity vs. block sensitivity (an average-case study)
From MaRDI portal
Publication:671409
DOI10.1016/0020-0190(96)00105-6zbMath0875.94140OpenAlexW2079828635MaRDI QIDQ671409
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
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
