4.2 Article

Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority

期刊

RANDOM STRUCTURES & ALGORITHMS
卷 48, 期 3, 页码 612-638

出版社

WILEY
DOI: 10.1002/rsa.20598

关键词

randomized decision tree; recursive majority

资金

  1. French ANR Blanc Project [ANR-12-BS02-005]
  2. European Commission IST STREP projects Quantum Computer Science (QCS) [25591]
  3. Quantum Algorithms (QALGO) [60070]
  4. NSERC Canada
  5. Government of Canada Through Industry Canada
  6. Province of Ontario through MRI
  7. Singapore Ministry of Education and National Research Foundation
  8. Tier 3 Grant Random Numbers from Quantum Process
  9. MTA RAMKI Lendulet Cryptography Research Group, NSERC
  10. Hungarian OTKA Grant [NN-102029]
  11. Zheijang Normal University

向作者/读者索取更多资源

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.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.2
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据