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.64946h. The previous best known algorithm achieved complexity (1.004) ·2.65622h. 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.
Partially supported by the French ANR Defis project ANR-08-EMER-012 (QRAC) and the European Commission IST STREP project 25596 (QSC).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Blum, M., Impagliazzo, R.: General oracle and oracle classes. In: Proc. FOCS 1987, pp. 118–126 (1987)
Hartmanis, J., Hemachandra, L.: One-way functions, robustness, and non-isomorphism of NP-complete sets. In: Proc. Struc. in Complexity Th. 1987, pp. 160–173 (1987)
Heiman, R., Newman, I., Wigderson, A.: On read-once threshold formulae and their randomized decision tree complexity. In: Proc. Struc. in Complexity Th. 1990, pp. 78–87 (1990)
Heiman, R., Wigderson, A.: Randomized versus deterministic decision tree complexity for read-once boolean functions. In: Proc. Struc. in Complexity Th. 1991, pp. 172–179 (1991)
Jayram, T., Kumar, R., Sivakumar, D.: Two applications of information complexity. In: Proc. STOC 2003, pp. 673–682 (2003)
Landau, I., Nachmias, A., Peres, Y., Vanniasegaram, S.: The lower bound for evaluating a recursive ternary majority function: an entropy-free proof. Tech. rep., Dep. of Stat., UC Berkeley (2006) (undergraduate Research Report), http://www.stat.berkeley.edu/110
Nisan, N.: CREW PRAMs and decision trees. In: Proc. STOC 1989, pp. 327–335. ACM, New York (1989)
Reichardt, B.W., Špalek, R.: Span-program-based quantum algorithm for evaluating formulas. In: Proc. 40th STOC, pp. 103–112. ACM, New York (2008)
Saks, M., Wigderson, A.: Probabilistic boolean decision trees and the complexity of evaluating game trees. In: Proc. FOCS 1986, pp. 29–38 (1986)
Santha, M.: On the Monte Carlo boolean decision tree complexity of read-once formulae. Random Structures and Algorithms 6(1), 75–87 (1995)
Snir, M.: Lower bounds for probabilistic linear decision trees. Combinatorica 9, 385–392 (1990)
Tardos, G.: Query complexity or why is it difficult to separate NP A ∩ coNP A from P A by a random oracle. Combinatorica 9, 385–392 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Magniez, F., Nayak, A., Santha, M., Xiao, D. (2011). Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority. In: Aceto, L., Henzinger, M., Sgall, J. (eds) Automata, Languages and Programming. ICALP 2011. Lecture Notes in Computer Science, vol 6755. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22006-7_27
Download citation
DOI: https://doi.org/10.1007/978-3-642-22006-7_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22005-0
Online ISBN: 978-3-642-22006-7
eBook Packages: Computer ScienceComputer Science (R0)