On randomized complexity of functions approximating the majority function

MaRDI QIDQ2746911zbMATH OpenFDO

Authors A. V. Chashkin

Publication date 11 October 2001

Published in Diskretnyĭ Analiz i Issledovanie Operatsiĭ. Seriya 1 (Search for Journal in Brave)

zbMATH Keywords

complexityRAMlower boundBoolean functionrandom number generator

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Stochastic Algorithms: Foundations and Applications
• On the complexity of finite random functions
• scientific article; zbMATH DE number 3916176
• scientific article; zbMATH DE number 11735
• Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority

Cited in

(3)

• Randomized algorithms for the majority problem
• On the complexity of finite random functions
• On approximate majority and probabilistic time

This page was built for publication: On randomized complexity of functions approximating the majority function

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