Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Interactive Proof Systems:
TR96-018 | 23rd February 1996
Oded Goldreich, Johan Håstad

On the Message Complexity of Interactive Proof Systems

Revisions: 2

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

TR97-031 | 9th September 1997
Oded Goldreich

On the Limits of Non-Approximability of Lattice Problems

Revisions: 2

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

TR01-096 | 21st November 2001
Jörg Rothe

Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial

Revisions: 1

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

TR04-007 | 13th January 2004
Alan L. Selman, Samik Sengupta

Polylogarithmic-round Interactive Proofs for coNP Collapses the Exponential Hierarchy

Revisions: 1 , Comments: 1

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

TR04-083 | 8th September 2004
Boaz Barak, Yehuda Lindell, Salil Vadhan

Lower Bounds for Non-Black-Box Zero Knowledge

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

TR12-091 | 16th July 2012
Abuzer Yakaryilmaz

One-counter verifiers for decidable languages

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

TR12-130 | 3rd October 2012
Abuzer Yakaryilmaz

Public-qubits versus private-coins

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

TR13-004 | 11th November 2012
A. C. Cem Say, Abuzer Yakaryilmaz

Finite state verifiers with constant randomness

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

TR17-101 | 8th June 2017
Oded Goldreich

On the doubly-efficient interactive proof systems of GKR

Revisions: 1

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

TR17-102 | 9th June 2017
Oded Goldreich

Overview of the doubly-efficient interactive proof systems of RRR

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

TR18-046 | 9th March 2018
Oded Goldreich, Guy Rothblum

Counting $t$-cliques: Worst-case to average-case reductions and Direct interactive proof systems

Revisions: 2

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

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

TR20-058 | 24th April 2020
Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, Amir Yehudayoff

Interactive Proofs for Verifying Machine Learning

We consider the following question: using a source of labeled data and interaction with an untrusted prover, what is the complexity of verifying that a given hypothesis is "approximately correct"? We study interactive proof systems for PAC verification, where a verifier that interacts with a prover is required to accept ... more >>>

ISSN 1433-8092 | Imprint