Research papers in computational complexity theory

• M. Bellare, O. Goldreich and E. Petrank.
  Uniform Generation of NP-witnesses using an NP-oracle. Information and Computation, Vol. 163, 2000, pp. 510--526.

• M. Bellare, R. Impagliazzo, and M. Naor.
  Does Parallel Repetition Lower the Error in Computationally Sound Protocols?
  Proceedings of 38th Annual Symposium on Foundations of Computer Science, IEEE, 1997.

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

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

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

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

• W. Aiello, M. Bellare and R. Venkatesan.
  Knowledge on the average: perfect, statistical and logarithmic.
  Proceedings 27th Annual Symposium on the Theory of Computing, ACM, 1995.

• M. Bellare, U. Feige and J. Kilian.
  On the role of shared randomness in two prover proof systems.
  Proceedings 3rd Israel Symposium on Theory and Computing Systems, IEEE, 1995.

• M. Bellare and J. Rompel.
  Randomness-efficient oblivious sampling.
  Proceedings 35th Annual Symposium on the Foundations of Computer Science, IEEE, 1994.

• M. Bellare and M. Sudan.
  Improved non-approximability results.
  Proceedings 26th Annual Symposium on the Theory of Computing, ACM, 1994.

• M. Bellare and S. Goldwasser.
  The complexity of decision versus search.
  SIAM J. on Computing, Vol. 23, No. 1, February 1994.

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

• M. Bellare.
  Interactive proofs and approximation: reductions from two provers in one round.
  Proceedings 2nd Israel Symposium on Theory and Computing Systems, IEEE, 1993.

• M. Bellare, S. Goldwasser, C. Lund and A. Russell.
  Efficient probabilistically checkable poofs and applications to approximation.
  Proceedings 25th Annual Symposium on the Theory of Computing, ACM, 1993.

• M. Bellare, O. Goldreich and S. Goldwasser.
  Randomness in interactive proofs.
  Computational Complexity, Vol. 3, No. 4, 1993, pp. 319--354.

• M. Bellare.
  A technique for upper bounding the spectral norm, with applications to learning.
  Proceedings of the Fifth Annual Workshop on Computational Learning Theory, ACM, 1992.

• M. Bellare and E. Petrank.
  Making zero-knowledge provers efficient.
  Proceedings 24th Annual Symposium on the Theory of Computing, ACM, 1992.