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

Boolean functioncomplexitylower boundRAMrandom number generator

Mathematics Subject Classification ID

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

Review text

The computational complexity of partial Boolean functions approximating the majority function by a modified RAM with a random number generator is considered. It is shown that there exist partial functions that approximate the majority function. The deterministic complexity of these functions exceeds their randomized complexity by the factor \(n\) (up to the order), where \(n\) is the number of variables of the Boolean functions under consideration.

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)

• On the complexity of finite random functions
• Randomized algorithms for the majority problem
• 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)