Improved bounds for the randomized decision tree complexity of recursive majority

DOI10.1002/RSA.20598zbMATH Open1338.05250MaRDI QIDQ2811168FDOQ2811168

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

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

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)

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

Cited In (5)

• Non-reversible stationary states for majority voter and Ising dynamics on trees
• Separation Between Deterministic and Randomized Query Complexity
• Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority
• Title not available (Why is that?)
• Computing majority by constant depth majority circuits with low fan-in gates

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)