Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority

DOI10.1007/978-3-642-22006-7_27MaRDI QIDQ3012816zbMATH OpenOpenAlexFDO

Authors Frédéric Magniez, Ashwin Nayak, Miklos Santha, David Xiao

Publication date 6 July 2011

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.7565, http://real.mtak.hu/44368/1/1309.7565v1.pdf

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: We consider the randomized decision tree complexity of the recursive 3-majority function. We prove a lower bound of $(1/2-delta)cdot2.57143^h$ for the two-sided-error randomized decision tree complexity of evaluating height $h$ formulae with error $deltain[0,1/2)$. This improves the lower bound of $(1-2delta)(7/3{)}^h$ given by Jayram, Kumar, and Sivakumar (STOC'03), and the one of $(1-2delta)cdot2.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)cdot2.64944^h$. The previous best known algorithm achieved complexity $(1.004)cdot2.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.

Recommendations

• Improved bounds for the randomized decision tree complexity of recursive majority
• An improved lower bound for the randomized decision tree complexity of recursive majority
• A lower bound for randomized algebraic decision trees
• scientific article; zbMATH DE number 1256781
• Optimal direct sum results for deterministic and randomized decision tree complexity
• Bounding the randomized decision tree complexity of read-once Boolean functions
• The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
• scientific article; zbMATH DE number 1098498
• On read-once threshold formulae and their randomized decision tree complexity
• Randomized Boolean decision trees: Several remarks

Cites work

• scientific article; zbMATH DE number 5485521 (Why is no real title available?)
• On read-once threshold formulae and their randomized decision tree complexity
• Query complexity, or why is it difficult to separate NP^ A coNP^ A from P^ A by random oracles A?
• Randomized vs. deterministic decision tree complexity for read-once Boolean functions
• Two applications of information complexity

Cited in

(6)

• On randomized complexity of functions approximating the majority function
• Improved bounds for the randomized decision tree complexity of recursive majority
• scientific article; zbMATH DE number 1256781 (Why is no real title available?)
• scientific article; zbMATH DE number 7250148 (Why is no real title available?)
• An improved lower bound for the randomized decision tree complexity of recursive majority
• Separating decision tree complexity from subcube partition complexity

This page was built for publication: Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3012816)