Improved bounds for the randomized decision tree complexity of recursive majority

Abstract

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 δ-two-sided-error randomized decision tree complexity of (1 - 2δ)(5/2) h , improving the lower bound of (1 - 2δ)(7/3) h given by Jayram, Kumar, and Sivakumar (STOC '03). Second, we improve the upper bound by giving a new zero-error randomized decision tree algorithm that has complexity at most (1.007) •2.64946 h . The previous best known algorithm achieved complexity (1.004) •2.65622 h . The new lower bound follows from a better analysis of the base case of the recursion of Jayram et al. The new algorithm uses a novel "interleaving" of two recursive algorithms. © 2011 Springer-Verlag.