Bellare - Publications in complexity theory

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 ( mihir@cs.ucsd.edu) and I can mail you a postscript file, or a hardcopy.

Survey Paper

1. [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.

Research Papers

1. [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, June 1998.

2. [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.

3. [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.

4. [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.

5. [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 ECCC.

6. [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.

7. [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, ACM, 1995.

8. [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.

9. [BeRm94] M. Bellare and J. Rompel. Randomness-efficient oblivious sampling. Proc. 35th Annual Symposium on the Foundations of Computer Science, IEEE, 1994.

10. [BeSu94] M. Bellare and M. Sudan. Improved non-approximability results. Proc. 26th Annual Symposium on the Theory of Computing, ACM, 1994.

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

12. [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.

13. [Be93] M. Bellare. Interactive proofs and approximation: reductions from two provers in one round. Proc. 2nd Israel Symposium on Theory and Computing Systems, IEEE, 1993.

14. [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, 1993.

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

16. [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.

17. [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