Name
Abstract | ||
|---|---|---|
We consider the randomized decision tree complexity of the recursive 3-majority function. We prove a lower bound of (1/2-delta) . 2.57143(h) for the two-sided-error randomized decision tree complexity of evaluating height h formulae with error delta is an element of [0, 1/2). This improves the lower bound of (1-2 delta)(7/3) h given by Jayram, Kumar, and Sivakumar (STOC'03), and the one of (1-2 delta) . 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. (C) 2015 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1002/rsa.20598 | RANDOM STRUCTURES & ALGORITHMS |
Keywords | Field | DocType |
randomized decision tree,recursive majority | Discrete mathematics,Decision tree,Combinatorics,Upper and lower bounds,Decision tree model,Element distinctness problem,Recursive partitioning,Decision tree learning,Mathematics,Recursion,Interleaving | Journal |
Volume | Issue | ISSN |
48.0 | 3.0 | 1042-9832 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frédéric Magniez | 1 | 570 | 44.33 |
| Ashwin Nayak | 2 | 645 | 61.76 |
| Miklos Santha | 3 | 728 | 92.42 |
| Jonah Sherman | 4 | 71 | 4.39 |
| Gábor Tardos | 5 | 1261 | 140.58 |
| David Xiao | 6 | 151 | 12.19 |