Improved bounds for the randomized decision tree Complexity of recursive majority

Magniez, Frédéric and Nayak, Ashwin and Santha, Miklos and Sherman, Jonah and Tardos, Gábor (2016) Improved bounds for the randomized decision tree Complexity of recursive majority. RANDOM STRUCTURES & ALGORITHMS, 48 (3). pp. 612-638. ISSN 1042-9832

Preview

Text 1309.7565v1.pdf Download (1MB) | Preview

Abstract

We consider the randomized decision tree complexity of the recursive 3-majority function. We prove a lower bound of inline image for the two-sided-error randomized decision tree complexity of evaluating height h formulae with error inline image. This improves the lower bound of inline image given by Jayram, Kumar, and Sivakumar (STOC'03), and the one of inline image 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 inline image. The previous best known algorithm achieved complexity inline image. 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.

Actions (login required)

Edit Item