An Improved Lower Bound for the Randomized Decision Tree Complexity of Recursive Majority

摘要

We prove that the randomized decision tree complexity of the recursive majority-of-three is Ω(2.55~d), 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 1986 paper on the complexity of evaluating game trees. Previous work includes an Ω((7/3)~d) lower bound, published in 2003 by Jayram, Kumar, and Sivakumar. Their proof used a top down induction and tools from information theory. In 2011, Magniez, Nayak, Santha, and Xiao, improved the lower bound to Ω((5/2)~d) and the upper bound to O(2.64946~d).