Under the auspices of the Computational Complexity Foundation (CCF)

TR05-129 | 30th October 2005
Scott Aaronson

#### QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols

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 ... more >>>

TR07-004 | 12th January 2007
Lance Fortnow, Rahul Santhanam

#### Time Hierarchies: A Survey

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

more >>>

TR08-075 | 7th July 2008
Olaf Beyersdorff, Johannes Köbler, Sebastian Müller

#### Nondeterministic Instance Complexity and Proof Systems with Advice

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 ... more >>>

TR09-064 | 3rd August 2009
Harry Buhrman, Lance Fortnow, Rahul Santhanam

#### Unconditional Lower Bounds against Advice

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 >>> TR09-092 | 8th October 2009 Olaf Beyersdorff, Johannes Köbler, Sebastian Müller #### Proof Systems that Take Advice 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 >>> TR10-057 | 1st April 2010 Scott Aaronson, Andrew Drucker #### A Full Characterization of Quantum Advice Revisions: 3 We prove the following surprising result: given any quantum state rho on n qubits, there exists a local Hamiltonian H on poly(n) qubits (e.g., a sum of two-qubit interactions), such that any ground state of H can be used to simulate rho on all quantum circuits of fixed polynomial size. ... more >>> TR14-171 | 11th December 2014 Lance Fortnow, Rahul Santhanam #### Hierarchies Against Sublinear Advice We strengthen the non-deterministic time hierarchy theorem of \cite{Cook72, Seiferas-Fischer-Meyer78, Zak83} to show that the lower bound holds against sublinear advice. More formally, we show that for any constants$c$and$d$such that$1 \leq c < d$, there is a language in$\NTIME(n^d)$which is not in$\NTIME(n^c)/n^{1/d}\$. ... more >>>

ISSN 1433-8092 | Imprint