A sensitivity estimate for Boolean functions

DOI10.1016/0898-1221(94)00139-1MaRDI QIDQ1334688zbMATH OpenOpenAlexFDO

Authors Włodek Bryc, Włodzimierz H. Smoleński

Publication date 25 September 1994

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0898-1221(94)00139-1

zbMATH Keywords

sensitivitycardinalityupper estimateFourier expansionBanzhaf indexKhinchin inequalityBoolean responserandom binary input

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68R99) Combinatorial probability (60C05)

Recommendations

• Boolean functions with low average sensitivity depend on few coordinates
• On learning monotone Boolean functions under the uniform distribution
• Quantitative relation between noise sensitivity and influences
• scientific article; zbMATH DE number 1966606

Cites work

• scientific article; zbMATH DE number 3165002 (Why is no real title available?)
• scientific article; zbMATH DE number 4067969 (Why is no real title available?)
• scientific article; zbMATH DE number 4106654 (Why is no real title available?)
• scientific article; zbMATH DE number 195103 (Why is no real title available?)
• scientific article; zbMATH DE number 274379 (Why is no real title available?)
• Mathematical Properties of the Banzhaf Power Index
• On the Best Possible Constants in the Khintchine Inequality for P ⩾ 3
• Some Bounds for the Banzhaf Index and Other Semivalues
• Spectral properties of threshold functions
• The best constants in the Khintchine inequality
• The influence of variables in product spaces

Cited in

(3)

• scientific article; zbMATH DE number 6850428 (Why is no real title available?)
• Boolean functions with low average sensitivity depend on few coordinates
• О методах оценивания веса булевых биюнктивных функций

This page was built for publication: A sensitivity estimate for Boolean functions

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