Pseudo-average block sensitivity equals average sensitivity

DOI10.1016/S0020-0190(98)00140-9MaRDI QIDQ293418zbMATH OpenFDO

Authors S. Venkatesh

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

sensitivityBoolean functioncombinatorial problemsblock sensitivity

Mathematics Subject Classification ID

Recommendations

• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• Sensitivity vs. block sensitivity of Boolean functions
• Boolean functions with low average sensitivity depend on few coordinates
• Tight bounds on sensitivity and block sensitivity of some classes of transitive functions
• Tight bounds on the average sensitivity of k-CNF

Cites work

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

Cited in

(1)

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

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

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