All reports by Author Mihir Bellare:

__
TR06-136
| 22nd October 2006
__

Mihir Bellare, Oded Goldreich#### On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge

__
TR98-032
| 10th June 1998
__

Mihir Bellare, Oded Goldreich, Erez Petrank#### Uniform Generation of NP-witnesses using an NP-oracle.

__
TR95-024
| 23rd May 1995
__

Mihir Bellare, Oded Goldreich, Madhu Sudan#### Free bits, PCP and Non-Approximability - Towards tight results

Revisions: 4

Mihir Bellare, Oded Goldreich

This note points out a gap between two natural formulations of

the concept of a proof of knowledge, and shows that in all

natural cases (e.g., NP-statements) this gap can be closed.

The aforementioned formulations differ by whether they refer to

(all possible) probabilistic or deterministic prover strategies.

Unlike ...
more >>>

Mihir Bellare, Oded Goldreich, Erez Petrank

A Uniform Generation procedure for $NP$ is an

algorithm which given any input in a fixed NP-language, outputs a uniformly

distributed NP-witness for membership of the input in the language.

We present a Uniform Generation procedure for $NP$ that runs in probabilistic

polynomial-time with an NP-oracle. This improves upon ...
more >>>

Mihir Bellare, Oded Goldreich, Madhu Sudan

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