Pseudo-average block sensitivity equals average sensitivity

DOI10.1016/S0020-0190(98)00140-9zbMATH Open1339.94102MaRDI QIDQ293418FDOQ293418

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

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

zbMATH Keywords

sensitivityBoolean functioncombinatorial problemsblock sensitivity

Mathematics Subject Classification ID

Cites Work

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

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)