REPORTS > KEYWORD > INTERACTIVE PROOFS:
Reports tagged with Interactive proofs:
TR94-007 | 12th December 1994
Oded Goldreich, Rafail Ostrovsky, Erez Petrank

#### Computational Complexity and Knowledge Complexity

We study the computational complexity of languages which have
interactive proofs of logarithmic knowledge complexity. We show that
all such languages can be recognized in ${\cal BPP}^{\cal NP}$. Prior
to this work, for languages with greater-than-zero knowledge
complexity (and specifically, even for knowledge complexity 1) only
trivial computational complexity bounds ... more >>>

TR94-008 | 12th December 1994
Oded Goldreich

#### Probabilistic Proof Systems (A Survey)

Various types of probabilistic proof systems have played
a central role in the development of computer science in the last decade.
In this exposition, we concentrate on three such proof systems ---
interactive proofs, zero-knowledge proofs,
and probabilistic checkable proofs --- stressing the essential
role of randomness in each ... more >>>

TR95-024 | 23rd May 1995
Mihir Bellare, Oded Goldreich, Madhu Sudan

#### Free bits, PCP and Non-Approximability - Towards tight results

Revisions: 4

This paper continues the investigation of the connection between proof
systems and approximation. The emphasis is on proving tight''
non-approximability results via consideration of measures like the
free bit complexity'' and the amortized free bit complexity'' of
proof systems.

The first part of the paper presents a collection of new ... more >>>

TR98-075 | 9th December 1998

#### Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses.

We establish hardness versus randomness trade-offs for a
broad class of randomized procedures. In particular, we create efficient
nondeterministic simulations of bounded round Arthur-Merlin games using
a language in exponential time that cannot be decided by polynomial
language with ... more >>>

TR99-025 | 2nd July 1999

#### Linear Consistency Testing

We extend the notion of linearity testing to the task of checking
linear-consistency of multiple functions. Informally, functions
are linear'' if their graphs form straight lines on the plane.
Two such functions are consistent'' if the lines have the same
slope. We propose a variant of a test of ... more >>>

TR01-046 | 2nd July 2001
Oded Goldreich, Salil Vadhan, Avi Wigderson

#### On Interactive Proofs with a Laconic Prover

We continue the investigation of interactive proofs with bounded
communication, as initiated by Goldreich and Hastad (IPL 1998).
Let $L$ be a language that has an interactive proof in which the prover
sends few (say $b$) bits to the verifier.
We prove that the complement $\bar L$ has ... more >>>

TR05-114 | 9th October 2005
Boaz Barak, Shien Jin Ong, Salil Vadhan

#### Derandomization in Cryptography

We give two applications of Nisan--Wigderson-type ("non-cryptographic") pseudorandom generators in cryptography. Specifically, assuming the existence of an appropriate NW-type generator, we construct:

A one-message witness-indistinguishable proof system for every language in NP, based on any trapdoor permutation. This proof system does not assume a shared random string or any ... more >>>

TR07-031 | 26th March 2007
Yael Tauman Kalai, Ran Raz

#### Interactive PCP

An interactive-PCP (say, for the membership $x \in L$) is a
proof that can be verified by reading only one of its bits, with the
help of a very short interactive-proof.
We show that for membership in some languages $L$, there are
interactive-PCPs that are significantly shorter than the known
more >>>

TR08-005 | 15th January 2008
Scott Aaronson, Avi Wigderson

#### Algebrization: A New Barrier in Complexity Theory

Any proof of P!=NP will have to overcome two barriers: relativization
and natural proofs. Yet over the last decade, we have seen circuit
lower bounds (for example, that PP does not have linear-size circuits)
that overcome both barriers simultaneously. So the question arises of
whether there ... more >>>

TR10-155 | 14th October 2010

#### Efficient Semantic Communication via Compatible Beliefs

In previous works, Juba and Sudan (STOC 2008) and Goldreich, Juba and Sudan (ECCC TR09-075) considered the idea of "semantic communication", wherein two players, a user and a server, attempt to communicate with each other without any prior common language (or communication protocol). They showed that if communication was goal-oriented ... more >>>

TR10-159 | 28th October 2010
Graham Cormode, Justin Thaler, Ke Yi

#### Verifying Computations with Streaming Interactive Proofs

Applications based on outsourcing computation require guarantees to the data owner that the desired computation has been performed correctly by the service provider. Methods based on proof systems can give the data owner the necessary assurance, but previous work does not give a sufficiently scalable and practical solution, requiring a ... more >>>

TR11-122 | 14th September 2011
Gillat Kol, Ran Raz

#### Competing Provers Protocols for Circuit Evaluation

Let $C$ be a (fan-in $2$) Boolean circuit of size $s$ and depth $d$, and let $x$ be an input for $C$. Assume that a verifier that knows $C$ but doesn't know $x$ can access the low degree extension of $x$ at one random point. Two competing provers try to ... more >>>

TR12-156 | 12th November 2012
Andrej Bogdanov, Chin Ho Lee

#### Limits of provable security for homomorphic encryption

Revisions: 1

We show that public-key bit encryption schemes which support weak homomorphic evaluation of parity or majority cannot be proved message indistinguishable beyond AM intersect coAM via general (adaptive) reductions, and beyond statistical zero-knowledge via reductions of constant query complexity.

Previous works on the limitation of reductions for proving security of ... more >>>

TR14-090 | 11th July 2014
Justin Thaler

#### Semi-Streaming Algorithms for Annotated Graph Streams

Revisions: 2

Considerable effort has been devoted to the development of streaming algorithms for analyzing massive graphs. Unfortunately, many results have been negative, establishing that a wide variety of problems require $\Omega(n^2)$ space to solve. One of the few bright spots has been the development of semi-streaming algorithms for a handful of ... more >>>

TR15-024 | 16th February 2015
Oded Goldreich, Tom Gur, Ron Rothblum

#### Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs

Proofs of proximity are probabilistic proof systems in which the verifier only queries a sub-linear number of input bits, and soundness only means that, with high probability, the input is close to an accepting input. In their minimal form, called Merlin-Arthur proofs of proximity (MAP), the verifier receives, in addition ... more >>>

ISSN 1433-8092 | Imprint