Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR12-099 | 3rd October 2012 17:46

An improved lower bound for the randomized decision tree complexity of recursive majority

RSS-Feed




Revision #1
Authors: Nikos Leonardos
Accepted on: 3rd October 2012 17:46
Downloads: 1087
Keywords: 


Abstract:

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)$.



Changes to previous version:

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$).


Paper:

TR12-099 | 5th August 2012 10:32

An improved lower bound for the randomized decision tree complexity of recursive majority





TR12-099
Authors: Nikos Leonardos
Publication: 10th August 2012 08:34
Downloads: 1116
Keywords: 


Abstract:

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)$.



ISSN 1433-8092 | Imprint