ECCC-Report TR10-192https://eccc.weizmann.ac.il/report/2010/192Comments and Revisions published for TR10-192en-usTue, 02 Jul 2013 09:56:06 +0300
Revision 1
| Improved bounds for the randomized decision tree complexity of recursive majority |
Frederic Magniez,
Ashwin Nayak,
Miklos Santha,
Jonah Sherman,
Gabor Tardos,
David Xiao
https://eccc.weizmann.ac.il/report/2010/192#revision1We consider the randomized decision tree complexity of the recursive 3-majority function. For evaluating height $h$ formulae, we prove a lower bound for the $\delta$-two-sided-error randomized decision tree complexity of $(1/2-\delta) \cdot 2.57143^h$, improving 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) \cdot 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) \cdot 2.64944^h$. The previous best known algorithm achieved complexity $(1.004) \cdot 2.65622^h$.
The new lower bound follows from a better analysis of the base case of the recursion of Jayram et al.The newalgorithm uses a novel ``interleaving'' of two recursive algorithms.
Tue, 02 Jul 2013 09:56:06 +0300https://eccc.weizmann.ac.il/report/2010/192#revision1
Paper TR10-192
| Improved bounds for the randomized decision tree complexity of recursive majority |
Frederic Magniez,
Ashwin Nayak,
Miklos Santha,
David Xiao
https://eccc.weizmann.ac.il/report/2010/192We consider the randomized decision tree complexity of the recursive 3-majority function. For evaluating a height $h$ formulae, we prove a lower bound for the $\delta$-two-sided-error randomized decision tree complexity of $(1-2\delta)(5/2)^h$, improving the lower bound of $(1-2\delta)(7/3)^h$ given by Jayram et al. (STOC '03). We also state a conjecture which would further improve the lower bound to $(1-2\delta)2.54355^h$.
Second, we improve the upper bound by giving a new zero-error randomized decision tree algorithm that has complexity at most $(1.007) \cdot 2.64946^h$, improving on the previous best known algorithm, which achieved $(1.004) \cdot 2.65622^h$.
Our lower bound follows from a better analysis of the base case of the recursion of Jayram et al. . Our algorithm uses a novel ``interleaving'' of two recursive algorithms.
Fri, 10 Dec 2010 10:00:54 +0200https://eccc.weizmann.ac.il/report/2010/192