Bellare - Publications in complexity theory
Here are my recent papers and surveys in complexity theory. This way
for a description of the underlying
research. Or back up to pointers to
my work in other areas.
Note: The papers below are stored as (gnu) compressed postscript.
Clicking ought to directly pop up a ghostview or enable you to save the file:
well-configured browsers seem to handle decompression and postscript
automatically. If things don't work, send me mail ( firstname.lastname@example.org) and I can mail you a
postscript file, or a hardcopy.
- [Be96] M. Bellare. Proof Checking and Approximation: Towards
Tight Results. This is a slightly expanded version of a survey
that appears in the Complexity Theory Column of Sigact News, Vol. 27,
No. 1, March 1996. Last updated September 1996.
- [BGP98] M. Bellare, O. Goldreich and E.
Petrank. Uniform Generation of NP-witnesses using an
NP-oracle. TR 98-032, Electronic Colloquium on Computational Complexity,
- [BIN97] M. Bellare, R. Impagliazzo,
and M. Naor. Does Parallel Repetition Lower
the Error in Computationally Sound Protocols? Full version. Extended
abstract in Proceedings of 38th Annual Symposium on Foundations of Computer
Science, IEEE, 1997.
- [BGR96] M. Bellare, J. Garay and
T. Rabin. Distributed pseudo-random bit
generators-- A new way to speed-up shared coin tossing.
Proceedings of the 15th ACM Symposium on Principles of Distributed
Computing, ACM, 1996.
- [BBHST] A. Bar-Noy, M. Bellare, M.
Halldorsson, H. Shachnai and T. Tamir. On chromatic
sums and distributed resource allocation. Information and
Computation, Vol. 140, No. 2, February 1998, pp. 183--202.
- [BGS95] M. Bellare, O. Goldreich and
M. Sudan. Free bits, PCPs and
non-approximability. SIAM J. on Computing, Vol. 27, No. 3, 1998,
pp. 804-915. Extended abstract was in FOCS 95. Many versions available on the
- [BCHKS95] M. Bellare,
D. Coppersmith, J. Hastad, M. Kiwi and M. Sudan. Linearity testing in characteristic two.
IEEE Transactions on Information Theory, Vol. 42, No. 6,
pp. 1781--1795, November 1996. Preliminary version in FOCS 95.
- [ABV95] W. Aiello, M. Bellare and
R. Venkatesan. Knowledge on the average:
perfect, statistical and logarithmic. Revised version. Preliminary
version in Proc. 27th Annual Symposium on the Theory of Computing,
- [BFK95] M. Bellare, U. Feige and
J. Kilian. On the role of shared
randomness in two prover proof systems. Proc. 3rd Israel
Symposium on Theory and Computing Systems, IEEE, 1995.
- [BeRm94] M. Bellare and J. Rompel.
Randomness-efficient oblivious sampling.
Proc. 35th Annual Symposium on the Foundations of Computer
Science, IEEE, 1994.
- [BeSu94] M. Bellare and M. Sudan.
Improved non-approximability results.
Proc. 26th Annual Symposium on the Theory of Computing,
- [BeGw94] M. Bellare and S. Goldwasser.
The complexity of decision versus search.
SIAM J. on Computing, Vol. 23, No. 1, February 1994.
- [BeRo93c] M. Bellare and P. Rogaway.
The complexity of approximating a nonlinear program.
Journal of Mathematical Programming B, Vol. 69, No. 3,
pp. 429-441, September 1995. Also in Complexity of Numerical
Optimization, ed. P. M. Pardalos, World Scientific, 1993.
- [Be93] M. Bellare.
Interactive proofs and approximation: reductions from
two provers in one round.
Proc. 2nd Israel Symposium on Theory and Computing Systems,
- [BGLR93] M. Bellare, S. Goldwasser,
C. Lund and A. Russell. Efficient
probabilistically checkable poofs and applications to
approximation. Revised version. Preliminary version in
Proc. 25th Annual Symposium on the Theory of Computing, ACM,
- [BGG93] M. Bellare, O. Goldreich and
S. Goldwasser. Randomness in interactive
proofs. Computational Complexity, Vol. 3, No. 4, 1993,
- [Be92] M. Bellare.
A technique for upper bounding the spectral
norm, with applications to learning.
Proc. of the Fifth Annual Workshop on Computational Learning
Theory, ACM, 1992.
- [BePe92] M. Bellare and E. Petrank.
Making zero-knowledge provers efficient.
Full paper. Preliminary version in Proc. 24th Annual Symposium
on the Theory of Computing, ACM, 1992.
Back to Mihir's home page