Improved bounds for the randomized decision tree Complexity of recursive majority
From MaRDI portal
Publication:2811168
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
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