We consider the randomized decision tree complexity of the recursive 3-majority function. For evaluating height $h$ formulae, we prove a lower bound for the $\delta$-two-sided-error randomized decision tree complexity of $(1/2-\delta) \cdot 2.57143^h$, improving the lower bound of $(1-2\delta)(7/3)^h$ given by Jayram, Kumar, and Sivakumar (STOC'03), and the one of $(1-2\delta) \cdot 2.55^h$ given by Leonardos (ICALP'13).

Second, we improve the upper bound by giving a new zero-error randomized decision tree algorithm that has complexity at most $(1.007) \cdot 2.64944^h$. The previous best known algorithm achieved complexity $(1.004) \cdot 2.65622^h$.

The new lower bound follows from a better analysis of the base case of the recursion of Jayram et al.The newalgorithm uses a novel ``interleaving'' of two recursive algorithms.

New co-authors and improved lower bounds.

We consider the randomized decision tree complexity of the recursive 3-majority function. For evaluating a height $h$ formulae, we prove a lower bound for the $\delta$-two-sided-error randomized decision tree complexity of $(1-2\delta)(5/2)^h$, improving the lower bound of $(1-2\delta)(7/3)^h$ given by Jayram et al. (STOC '03). We also state a conjecture which would further improve the lower bound to $(1-2\delta)2.54355^h$.

Second, we improve the upper bound by giving a new zero-error randomized decision tree algorithm that has complexity at most $(1.007) \cdot 2.64946^h$, improving on the previous best known algorithm, which achieved $(1.004) \cdot 2.65622^h$.

Our lower bound follows from a better analysis of the base case of the recursion of Jayram et al. . Our algorithm uses a novel ``interleaving'' of two recursive algorithms.