Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > GENERALIZED COSTS:
Reports tagged with Generalized costs:
TR12-099 | 5th August 2012
Nikos Leonardos

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

Revisions: 1

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 ... more >>>




ISSN 1433-8092 | Imprint