An Improved Lower Bound for the Randomized Decision Tree Complexity of Recursive Majority,

DOI10.1007/978-3-642-39206-1_59zbMath1336.68103OpenAlexW1022052099MaRDI QIDQ5326603

Nikos Leonardos

Publication date: 6 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-39206-1_59

zbMATH Keywords

Boolean functionslower boundsrandomized computationquery complexitydecision tree complexitygeneralized costs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Unnamed Item

This page was built for publication: An Improved Lower Bound for the Randomized Decision Tree Complexity of Recursive Majority,