We consider noninteractive zero-knowledge proofs in the shared random
string model proposed by Blum, Feldman and Micali \cite{bfm}. Until
recently there was a sizable polynomial gap between the most
efficient noninteractive proofs for {\sf NP} based on general
complexity assumptions \cite{fls} versus those based on specific
algebraic assumptions \cite{Da}. ... more >>>

We consider some problems about pairs of disjoint $NP$ sets.
The theory of these sets with a natural concept of reducibility
is, on the one hand, closely related to the theory of proof
systems for propositional calculus, and, on the other, it
resembles the theory of NP completeness. Furthermore, such
more >>>

We define propositional quantum Frege proof systems and compare it
with classical Frege proof systems.

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

We present three contributions to the understanding of QMA with multiple provers:

1) We give a tight soundness analysis of the protocol of [Blier and Tapp, ICQNM '09], yielding a soundness gap $\Omega(N^{-2})$, which is the best-known soundness gap for two-prover QMA protocols with logarithmic proof size. Maybe ... more >>>