Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR98-032 | 10th June 1998
Mihir Bellare, Oded Goldreich, Erez Petrank

Uniform Generation of NP-witnesses using an NP-oracle.

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

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

ISSN 1433-8092 | Imprint