Quadratically tight relations for randomized query complexity
From MaRDI portal
Publication:5915578
DOI10.1007/978-3-319-90530-3_18zbMath1434.68198arXiv1708.00822OpenAlexW2741419985WikidataQ58040173 ScholiaQ58040173MaRDI QIDQ5915578
Hartmut Klauck, Troy Lee, Miklos Santha, Srijita Kundu, Jevgēnijs Vihrovs, Rahul Jain, Swagato Sanyal
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 algorithmsquery complexitycertificate complexitycorruption boundfractional block sensitivity
Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Classical models of computation (Turing machines, etc.) (68Q04)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
- Composition limits and separating examples for some Boolean function complexity measures
- Complexity measures and decision tree complexity: a survey.
- Quantum certificate complexity
- Properties and applications of boolean function composition
- Separations in query complexity using cheat sheets
- Quantum lower bounds by polynomials