Please use this identifier to cite or link to this item:
|Title:||Improved bounds for the randomized decision tree complexity of recursive majority|
|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)|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Jan 17, 2018
checked on Jan 21, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.