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
|
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.
Item Type: | Article |
---|---|
Additional Information: | Article first published online: 8 JUL 2015 |
Uncontrolled Keywords: | recursive majority; randomized decision tree |
Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
SWORD Depositor: | MTMT SWORD |
Depositing User: | MTMT SWORD |
Date Deposited: | 03 Jan 2017 18:15 |
Last Modified: | 03 Jan 2017 18:15 |
URI: | http://real.mtak.hu/id/eprint/44368 |
Actions (login required)
![]() |
Edit Item |