VLDB 2026 Research / reviewers in the wild / expert
DeVon Ingram
dblp:211/6934
· DBLP profile ↗
1ranked-venue papers
0as first author
1since 2021 · last 2022
—ORCID · unresolved
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 1 · 1 since 2021
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Theoretical computer science
1 paper |
Computational complexity · 56% Quantum computing and quantum information · 44% |
Topics — the 6 heaviest of 6, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Computational complexity › complexity classes
BQP |
0.6 | 1 | 2022 | The Acrobatics of BQP · CCC 2022 |
Computational complexity › relativization
oracle separation |
0.6 | 1 | 2022 | The Acrobatics of BQP · CCC 2022 |
Quantum computing and quantum information › quantum computing
quantum complexity classes |
0.6 | 1 | 2022 | The Acrobatics of BQP · CCC 2022 |
Quantum computing and quantum information
quantum computing |
0.6 | 1 | 2022 | The Acrobatics of BQP · CCC 2022 |
Computational complexity › circuit complexity › constant-depth circuits
AC0 |
0.2 | 1 | 2022 | The Acrobatics of BQP · CCC 2022 |
Computational complexity
circuit complexity |
0.2 | 1 | 2022 | The Acrobatics of BQP · CCC 2022 |
Methods — techniques the papers use, named apart from their topics
random restriction method · 0.6forrelation problem · 0.6block sensitivity · 0.6
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2022 | The Acrobatics of BQPabstractOne can fix the randomness used by a randomized algorithm, but there is no analogous notion of fixing the quantumness used by a quantum algorithm. Underscoring this fundamental difference, we show that, in the black-box setting, the behavior of quantum polynomial-time ($\mathsf{BQP}$) can be remarkably decoupled from that of classical complexity classes like $\mathsf{NP}$. Specifically: -There exists an oracle relative to which $\mathsf{NP^{BQP}}\not\subset\mathsf{BQP^{PH}}$, resolving a 2005 problem of Fortnow. As a corollary, there exists an oracle relative to which $\mathsf{P}=\mathsf{NP}$ but $\mathsf{BQP}\neq\mathsf{QCMA}$. -Conversely, there exists an oracle relative to which $\mathsf{BQP^{NP}}\not\subset\mathsf{PH^{BQP}}$. -Relative to a random oracle, $\mathsf{PP}=\mathsf{PostBQP}$ is not contained in the "$\mathsf{QMA}$ hierarchy" $\mathsf{QMA}^{\mathsf{QMA}^{\mathsf{QMA}^{\cdots}}}$. -Relative to a random oracle, $\mathsfΣ_{k+1}^\mathsf{P}\not\subset\mathsf{BQP}^{\mathsfΣ_{k}^\mathsf{P}}$ for every $k$. -There exists an oracle relative to which $\mathsf{BQP}=\mathsf{P^{\# P}}$ and yet $\mathsf{PH}$ is infinite. -There exists an oracle relative to which $\mathsf{P}=\mathsf{NP}\neq\mathsf{BQP}=\mathsf{P^{\# P}}$. To achieve these results, we build on the 2018 achievement by Raz and Tal of an oracle relative to which $\mathsf{BQP}\not \subset \mathsf{PH}$, and associated results about the Forrelation problem. We also introduce new tools that might be of independent interest. These include a "quantum-aware" version of the random restriction method, a concentration theorem for the block sensitivity of $\mathsf{AC^0}$ circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles. Scott Aaronson, DeVon Ingram, William Kretschmer |
CCC | 2 |