Improved bounds for the randomized decision tree Complexity of recursive majority

DOI10.1002/rsa.20598zbMath1338.05250MaRDI QIDQ2811168

Ashwin Nayak, Miklos Santha, Gábor Tardos, Jonah Sherman, David Xiao, Frédéric Magniez

Publication date: 10 June 2016

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: http://real.mtak.hu/44368/1/1309.7565v1.pdf

zbMATH Keywords

randomized decision treerecursive majority

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Separation Between Deterministic and Randomized Query Complexity ⋮ Computing majority by constant depth majority circuits with low fan-in gates

Cites Work

• Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
• Lower bounds on probabilistic linear decision trees
• Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority