Improved bounds for the randomized decision tree complexity of recursive majority

DOI10.1002/RSA.20598MaRDI QIDQ2811168zbMATH OpenFDO

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

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

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
• Randomized Boolean decision trees: Several remarks
• The quantum black-box complexity of majority
• Bounding the randomized decision tree complexity of read-once Boolean functions

Cites work

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

Cited in

(6)

• scientific article; zbMATH DE number 1256781 (Why is no real title available?)
• Non-reversible stationary states for majority voter and Ising dynamics on trees
• Computing majority by constant depth majority circuits with low fan-in gates
• Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority
• An improved lower bound for the randomized decision tree complexity of recursive majority
• Separation between deterministic and randomized query 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 Q2811168)