Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority

Recursive Majority-of-three (3-Maj) is a deceptively simple problem in the study of randomized decision tree complexity. The precise complexity of this problem is unknown, while that of the similarly defined Recursive NAND tree is completely understood.

We revisit 3-Maj with the goal of understanding the nature of randomized algorithms. We prove a lower bound of (1-2d)(5/2)^h for bounded error-d randomized algorithms for evaluating a height h formula. This improves over the best known bound of (1-2d)(7/3)^h due to Jayram, Kumar, and Sivakumar (2003). We also present a zero-error randomized algorithm with complexity roughly 2.649^h; where the previous best bound was roughly 2.656^h. These improvements are obtained by extending the techniques due to Jayram et al. in novel ways.

It is worth noting that the complexity of 3-Maj in the quantum analogue of the model is also well-characterized. Our work illustrates that unlike the quantum algorithm for the problem and the classical one for Recursive NAND, the optimal randomized algorithm for 3-Maj is unlikely to have a simple recursive structure.

This is joint work with Frederic Magniez, Miklos Santha, and David Xiao.