Pseudo-average block sensitivity equals average sensitivity

DOI10.1016/S0020-0190(98)00140-9zbMath1339.94102MaRDI QIDQ293418

F. Blanchet-Sadri, M. Dambrine

Publication date: 9 June 2016

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

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098001409?np=y

zbMATH Keywords

sensitivitycombinatorial problemsBoolean functionblock sensitivity

Mathematics Subject Classification ID

Related Items (1)

Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables

Cites Work

• The average sensitivity of bounded-depth circuits
• Sensitivity vs. block sensitivity (an average-case study)
• Sensitivity vs. block sensitivity of Boolean functions
• Constant depth circuits, Fourier transform, and learnability
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• CREW PRAM<scp>s</scp> and Decision Trees

This page was built for publication: Pseudo-average block sensitivity equals average sensitivity