The \emph{Orbit problem} is defined as follows: Given a matrix $A\in
\Q ^{n\times n}$ and vectors $\x,\y\in \Q ^n$, does there exist a
non-negative integer $i$ such that $A^i\x=\y$. This problem was
shown to be in deterministic polynomial time by Kannan and Lipton in
\cite{KL1986}. In this paper we place ... more >>>

The class QMA(k), introduced by Kobayashi et al., consists
of all languages that can be verified using k unentangled quantum
proofs. Many of the simplest questions about this class have remained
embarrassingly open: for example, can we give any evidence that k
quantum proofs are more powerful than one? Can ... more >>>

We develop new tools to study the relative complexities of secure
multi-party computation tasks (functionalities) in the Universal
Composition framework. When one task can be securely realized using
another task as a black-box, we interpret this as a
qualitative, complexity-theoretic reduction between the two tasks.
Virtually all previous characterizations of ... more >>>