Does Parallel Repetition Lower the Error in Computationally Sound Protocols?
Proceedings of 38th Annual Symposium on Foundations of Computer Science, IEEE, 1997.
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.
On chromatic sums and distributed resource allocation.
Information and Computation, Vol. 140, No. 2, February 1998, pp. 183--202.
Free bits, PCPs and non-approximability.
SIAM J. on Computing, Vol. 27, No. 3, 1998, pp. 804-915.
Linearity testing in characteristic two.
IEEE Transactions on Information Theory, Vol. 42, No. 6, pp. 1781--1795, November 1996.
Knowledge on the average: perfect, statistical and logarithmic.
Proceedings 27th Annual Symposium on the Theory of Computing, ACM, 1995.
On the role of shared randomness in two prover proof systems.
Proceedings 3rd Israel Symposium on Theory and Computing Systems, IEEE, 1995.
Randomness-efficient oblivious sampling.
Proceedings 35th Annual Symposium on the Foundations of Computer Science, IEEE, 1994.
Improved non-approximability results.
Proceedings 26th Annual Symposium on the Theory of Computing, ACM, 1994.
The complexity of decision versus search.
SIAM J. on Computing, Vol. 23, No. 1, February 1994.
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.
Interactive proofs and approximation: reductions from two provers in one round.
Proceedings 2nd Israel Symposium on Theory and Computing Systems, IEEE, 1993.
Efficient probabilistically checkable poofs and applications to approximation.
Proceedings 25th Annual Symposium on the Theory of Computing, ACM, 1993.
Randomness in interactive proofs.
Computational Complexity, Vol. 3, No. 4, 1993, pp. 319--354.
A technique for upper bounding the spectral norm, with applications to learning.
Proceedings of the Fifth Annual Workshop on Computational Learning Theory, ACM, 1992.
Making zero-knowledge provers efficient.
Proceedings 24th Annual Symposium on the Theory of Computing, ACM, 1992.