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.