Name
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.
|
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-22006-7_27 | ICALP'11 Proceedings of the 38th international colloquim conference on Automata, languages and programming - Volume Part I |
Keywords | Field | DocType |
new zero-error randomized decision,base case,recursive majority,recursive algorithm,3-majority function,improved bound,tree algorithm,two-sided-error randomized decision tree,new algorithm,height h formula,better analysis,randomized decision tree complexity,lower bound,decision tree,upper bound | Decision tree,Combinatorics,Decision tree model,Element distinctness problem,Recursive partitioning,Recursion,Mathematics | Journal |
Volume | ISSN | Citations |
abs/1309.7565 | 0302-9743 | 2 |
PageRank | References | Authors |
0.44 | 7 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frédéric Magniez | 1 | 570 | 44.33 |
| Ashwin Nayak | 2 | 645 | 61.76 |
| Miklos Santha | 3 | 728 | 92.42 |
| David Xiao | 4 | 151 | 12.19 |