Improved bounds for the randomized decision tree Complexity of recursive majority

We consider the randomized decision tree complexity of the recursive 3‐majority function. We prove a lower bound of ( 1 / 2 − δ ) · 2.57143 hfor the two‐sided‐error randomized decision tree complexity of evaluating height h formulae with error δ ∈ [ 0 , 1 / 2 ) . This improves the lower bound of ( 1 − 2 δ ) ( 7 / 3 ) hgiven by Jayram, Kumar, and Sivakumar (STOC'03), and the one of ( 1 − 2 δ ) · 2.55 hgiven 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 ) · 2.64944 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. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 612–638, 2016