An Improved Lower Bound for the Randomized Decision Tree Complexity of Recursive Majority,
From MaRDI portal
Publication:5326603
DOI10.1007/978-3-642-39206-1_59zbMath1336.68103MaRDI QIDQ5326603
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
Boolean functions; lower bounds; randomized computation; query complexity; decision tree complexity; generalized costs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)