Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR10-192 | 2nd July 2013 09:56

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

Revision #1
Authors: Frederic Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gabor Tardos, David Xiao
Accepted on: 2nd July 2013 09:56
Keywords:

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 $\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.

Changes to previous version:

New co-authors and improved lower bounds.

### Paper:

TR10-192 | 8th December 2010 20:39

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

TR10-192
Authors: Frederic Magniez, Ashwin Nayak, Miklos Santha, David Xiao
Publication: 10th December 2010 10:00
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint