文章基本信息
- 标题：An improved lower bound for the randomized decision tree complexity of recursive majority
- 本地全文：下载
- 作者：Nikos Leonardos
- 期刊名称：Electronic Colloquium on Computational Complexity
- 印刷版ISSN：1433-8092
- 出版年度：2012
- 卷号：2012
- 出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
- 摘要：
We prove that the randomized decision tree complexity of the recursive majority-of-three is (255d), where d is the depth of the recursion. The proof is by a bottom up induction, which is same in spirit as the one in the proof of Saks and Wigderson in their FOCS 1986 paper on the complexity of valuating game trees.
Previous work includes an ((73)d) lower bound, presented in STOC 2003 by Jayram, Kumar, and Sivakumar. Their proof used a top down induction and tools from information theory. In ICALP 2011, Magniez, Nayak, Santha, and Xiao, improved the lower bound to ((52)d) and the upper bound to O(264946d).
- 关键词：Boolean Functions; decision tree complexity; Generalized costs; query complexity; Randomized Computation
