Quadratically tight relations for randomized query complexity
From MaRDI portal
Publication:5915578
DOI10.1007/978-3-319-90530-3_18zbMath1434.68198arXiv1708.00822WikidataQ58040173 ScholiaQ58040173MaRDI QIDQ5915578
Troy Lee, Rahul Jain, Hartmut Klauck, Miklos Santha, Swagato Sanyal, Srijita Kundu, Jevgēnijs Vihrovs
Publication date: 28 November 2018
Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1708.00822
randomized algorithms; query complexity; certificate complexity; corruption bound; fractional block sensitivity
68Q25: Analysis of algorithms and problem complexity
68W20: Randomized algorithms
68Q04: Classical models of computation (Turing machines, etc.)