Publication:5915578: Difference between revisions
From MaRDI portal
Publication:5915578
Created automatically from import240129110113 |
EloiFerrer (talk | contribs) m EloiFerrer moved page Quadratically tight relations for randomized query complexity to Quadratically tight relations for randomized query complexity: Duplicate |
(No difference)
|
Latest revision as of 14:42, 2 May 2024
DOI10.1007/978-3-319-90530-3_18zbMath1434.68198arXiv1708.00822WikidataQ58040173 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 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.)
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item