We prove that the randomized decision tree complexity of the recursive majority-of-three is $\Omega(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 FOCS 1986 paper on the complexity of valuating game trees.

Previous work includes an $\Omega((7/3)^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 $\Omega((5/2)^d)$ and the upper bound to $O(2.64946^d)$.

An error in the proof of Corollary 6 was pointed out to the author by Jeff Steif. The error is fixed in the new version, but a weaker lower-bound is proved ($2.55^d$ instead of $2.6^d$).

We prove that the randomized decision tree complexity of the recursive majority-of-three is $\Omega(2.6^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 FOCS 1986 paper on the complexity of valuating game trees.

Previous work includes an $\Omega((7/3)^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 $\Omega((5/2)^d)$ and the upper bound to $O(2.64946^d)$.