Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-22006-7_27
Title: Improved bounds for the randomized decision tree complexity of recursive majority
Authors: Magniez, F.
Nayak, A.
Santha, M. 
Xiao, D.
Issue Date: 2011
Source: Magniez, F.,Nayak, A.,Santha, M.,Xiao, D. (2011). Improved bounds for the randomized decision tree complexity of recursive majority. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6755 LNCS (PART 1) : 317-329. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-22006-7_27
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 δ-two-sided-error randomized decision tree complexity of (1 - 2δ)(5/2) h , improving the lower bound of (1 - 2δ)(7/3) h given by Jayram, Kumar, and Sivakumar (STOC '03). Second, we improve the upper bound by giving a new zero-error randomized decision tree algorithm that has complexity at most (1.007) •2.64946 h . The previous best known algorithm achieved complexity (1.004) •2.65622 h . 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. © 2011 Springer-Verlag.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/117252
ISBN: 9783642220050
ISSN: 03029743
DOI: 10.1007/978-3-642-22006-7_27
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

3
checked on Jan 17, 2018

Page view(s)

32
checked on Jan 21, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.