Chris Pollett

Variants of Kannan's Theorem are given where the circuits of

the original theorem are replaced by arbitrary recursively presentable

classes of languages that use advice strings and satisfy certain mild

conditions. These variants imply that $\DTIME(n^{k'})^{\NE}/n^k$

does not contain $\PTIME^{\NE}$, $\DTIME(2^{n^{k'}})/n^k$ does

not contain $\EXP$, $\SPACE(n^{k'})/n^k$ does not ...
more >>>

Scott Aaronson, Harry Buhrman, William Kretschmer

Relational problems (those with many possible valid outputs) are different from decision problems, but it is easy to forget just how different. This paper initiates the study of FBQP/qpoly, the class of relational problems solvable in quantum polynomial-time with the help of polynomial-sized quantum advice, along with its analogues for ... more >>>