Oded Goldreich, Johan Hastad

We investigate the computational complexity of languages

which have interactive proof systems of bounded message complexity.

In particular, we show that

(1) If $L$ has an interactive proof in which the total

communication is bounded by $c(n)$ bits

then $L$ can be recognized a probabilitic machine

in time ...
more >>>

Oded Goldreich

We show simple constant-round interactive proof systems for

problems capturing the approximability, to within a factor of $\sqrt{n}$,

of optimization problems in integer lattices; specifically,

the closest vector problem (CVP), and the shortest vector problem (SVP).

These interactive proofs are for the ``coNP direction'';

that is, ...
more >>>

Jörg Rothe

In this tutorial, selected topics of cryptology and of

computational complexity theory are presented. We give a brief overview

of the history and the foundations of classical cryptography, and then

move on to modern public-key cryptography. Particular attention is

paid to cryptographic protocols and the problem of constructing ...
more >>>

Alan L. Selman, Samik Sengupta

It is known \cite{BHZ87} that if every language in coNP has a

constant-round interactive proof system, then the polynomial hierarchy

collapses. On the other hand, Lund {\em et al}.\ \cite{LFKN92} have shown that

#SAT, the #P-complete function that outputs the number of satisfying

assignments of a Boolean ...
more >>>

Boaz Barak, Yehuda Lindell, Salil Vadhan

We show new lower bounds and impossibility results for general (possibly <i>non-black-box</i>) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions:

<ol>

<li> There does not exist a two-round zero-knowledge <i>proof</i> system with perfect completeness for an NP-complete language. The previous impossibility result for two-round zero ...
more >>>

Abuzer Yakaryilmaz

Condon and Lipton (FOCS 1989) showed that the class of languages having a space-bounded interactive proof system (IPS) is a proper subset of decidable languages, where the verifier is a probabilistic Turing machine. In this paper, we show that if we use architecturally restricted verifiers instead of restricting the working ... more >>>

Abuzer Yakaryilmaz

We introduce a new public quantum interactive proof system, namely qAM, by augmenting the verifier with a fixed-size quantum register in Arthur-Merlin game. We focus on space-bounded verifiers, and compare our new public system with private-coin interactive proof (IP) system in the same space bounds. We show that qAM systems ... more >>>

A. C. Cem Say, Abuzer Yakaryilmaz

We give a new characterization of NL as the class of languages whose members have certificates that can be verified with small error in polynomial time by finite state machines that use a constant number of random bits, as opposed to its conventional description in terms of deterministic logarithmic-space verifiers. ... more >>>

Oded Goldreich

We present a somewhat simpler variant of the doubly-efficient interactive proof systems of Goldwasser, Kalai, and Rothblum (JACM, 2015).

Recall that these proof systems apply to log-space uniform sets in NC (or, more generally, to inputs that are acceptable by log-space uniform bounded-depth circuits, where the number of rounds in ...
more >>>

Oded Goldreich

We provide an overview of the doubly-efficient interactive proof systems of Reingold, Rothblum, and Rothblum (STOC, 2016).

Recall that by their result, any set that is decidable in polynomial-time by an algorithm of space complexity $s(n)\leq n^{0.499}$, has a constant-round interactive proof system

in which the prover runs polynomial time ...
more >>>

Oded Goldreich, Guy Rothblum

We present two main results regarding the complexity of counting the number of $t$-cliques in a graph.

\begin{enumerate}

\item{\em A worst-case to average-case reduction}:

We reduce counting $t$-cliques in any $n$-vertex graph to counting $t$-cliques in typical $n$-vertex graphs that are drawn from a simple distribution of min-entropy ${\widetilde\Omega}(n^2)$. For ...
more >>>