# Improved bounds for the randomized decision tree complexity of recursive majority

arXiv: https://arxiv.org/abs/1309.7565 · HTML: https://mlsanity.com/paper/1309.7565/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Sep 2013.

## Built on by (most cited first, 2 of 2)

- [On the Trade-off between the Number of Nodes and the Number of Trees in a Random Forest](https://mlsanity.com/paper/2312.11540/) (2023)
- [Query-efficient winner prediction in district-based elections](https://mlsanity.com/paper/2610.00577/) (2026)

## Abstract (arXiv)

We consider the randomized decision tree complexity of the recursive 3-majority function. We prove a lower bound of (1/2-δ) · 2.57143h for 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)h given by Jayram, Kumar, and Sivakumar (STOC'03), and the one of (1-2δ) · 2.55h 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) · 2.64944h. The previous best known algorithm achieved complexity (1.004) · 2.65622h. 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.