This paper introduces a new technique for removing existential quantifiers over quantum states. Using this technique, we show that there is no way to pack an exponential number of bits into a polynomial-size quantum state, in such a way that the value of any one of those bits can later ... more >>>

We survey time hierarchies, with an emphasis on recent attempts to prove hierarchies for semantic classes. more >>>

Motivated by strong Karp-Lipton collapse results in bounded arithmetic, Cook and Krajicek have recently introduced the notion of propositional proof systems with advice. In this paper we investigate the following question: Do there exist polynomially bounded proof systems with advice for arbitrary languages? Depending on the complexity of the underlying ... more >>>

We show several unconditional lower bounds for exponential time classes against polynomial time classes with advice, including: \begin{enumerate} \item For any constant $c$, $\NEXP \not \subseteq \P^{\NP[n^c]}/n^c$ \item For any constant $c$, $\MAEXP \not \subseteq \MA/n^c$ \item $\BPEXP \not \subseteq \BPP/n^{o(1)}$ \end{enumerate} It was previously unknown even whether $\NEXP \subseteq ... more >>>

One of the starting points of propositional proof complexity is the seminal paper by Cook and Reckhow (JSL 79), where they defined propositional proof systems as poly-time computable functions which have all propositional tautologies as their range. Motivated by provability consequences in bounded arithmetic, Cook and Krajicek (JSL 07) have ... more >>>