Premium
Improved bounds for the randomized decision tree Complexity of recursive majority
Author(s) -
Magniez Frédéric,
Nayak Ashwin,
Santha Miklos,
Sherman Jonah,
Tardos Gábor,
Xiao David
Publication year - 2016
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20598
Subject(s) - interleaving , mathematics , upper and lower bounds , recursion (computer science) , decision tree , tree (set theory) , time complexity , randomized algorithm , decision tree model , combinatorics , discrete mathematics , algorithm , computer science , artificial intelligence , mathematical analysis , operating system
We consider the randomized decision tree complexity of the recursive 3‐majority function. We prove a lower bound of ( 1 / 2 − δ ) · 2.57143 hfor 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 ) hgiven by Jayram, Kumar, and Sivakumar (STOC'03), and the one of ( 1 − 2 δ ) · 2.55 hgiven 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