Improved bounds for the randomized decision tree Complexity of recursive majority 12. Issue 3 (8th July 2015)

• Record Type: Journal Article
• Authors: Magniez, Frédéric; Nayak, Ashwin; Santha, Miklos; Sherman, Jonah; Tardos, Gábor; Xiao, David
• Is Part Of: Random structures & algorithms. Volume 48:Issue 3(2016)
• Page Start: 612
• Page End: 638
• Publication Date: 2015-07-08
• Subjects: randomized decision tree -- recursive majority; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20598
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We consider the randomized decision tree complexity of the recursive 3‐majority function. We prove a lower bound of ( 1 / 2 − δ ) · 2.57143 h for the two‐sided‐error randomized decision tree complexity of evaluating height h formulae with error δ ∈ [ 0, 1 / 2 ) . This improves the lower bound of ( 1 − 2 δ ) ( 7 / 3 ) h given by Jayram, Kumar, and Sivakumar (STOC'03), and the one of ( 1 − 2 δ ) · 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 ) · 2.64944 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. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 612–638, 2016