Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority

DOI10.1007/978-3-642-22006-7_27zbMath1332.68085arXiv1309.7565OpenAlexW1946549189MaRDI QIDQ3012816

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

Mathematics Subject Classification ID

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

Related Items (2)

Improved bounds for the randomized decision tree Complexity of recursive majority ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Randomized vs. deterministic decision tree complexity for read-once Boolean functions
• Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
• On read-once threshold formulae and their randomized decision tree complexity
• Two applications of information complexity

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