Theoretical computer scientists have been debating the role of
oracles since the 1970's. This paper illustrates both that oracles
can give us nontrivial insights about the barrier problems in
circuit complexity, and that they need not prevent us from trying to
solve those problems.

First, we ... more >>>

We study the approximate-coloring(q,Q) problem: Given a graph G, decide
whether \chi(G) \le q or \chi(G)\ge Q. We derive conditional
hardness for this problem for any constant 3\le q < Q. For q \ge
4, our result is based on Khot's 2-to-1 conjecture [Khot'02].
For q=3, we base our hardness ... more >>>

We show how to encode $2^n$ (classical) bits $a_1,...,a_{2^n}$
by a single quantum state $|\Psi \rangle$ of size $O(n)$ qubits,
such that:
for any constant $k$ and any $i_1,...,i_k \in \{1,...,2^n\}$,
the values of the bits $a_{i_1},...,a_{i_k}$ can be retrieved
from $|\Psi \rangle$ by a one-round Arthur-Merlin interactive ... more >>>