Schedule for Spring 2001
Topic: Interactive Proofs
For those that did not attend my presentation of this subject in the
fall term: Interactive proofs have to
do with the problem of "How to convince?". The assumption is to have an
omniscient prover that can help one to find answers to otherwise intractable
problems, but the demand is to be at least CONVINCED by the prover that
his answer is correct. It turns out that this can be a difficult task...
Meetings:
The meetings will take place every Wednesday at 4 p.m. in NEB 325.
Papers revolving around interactive proofs:
If you find an interesting paper you would like
to read (as a single or a group) and present (as a whole or in part) in a
meeting, let me know and I reserve it for you.
You can get credit for your work if you want to by registering for the
Seminar in
Theory (number 600.771, see also the
spring 01
course offerings of the CS department).
Some introductory text to interactive proofs:
The two papers that introduced interactive proofs:
Interactive proofs and complexity:
- S. Goldwasser and M. Sipser.
Private coins versus public coins in interactive
proof systems.
In STOC 86, 59-68, 1986.
- L. Babai, L. Fortnow, and C. Lund.
Non-deterministic exponential time has two-prover
interactive proofs.
In Computational Complexity 1(1):3-40, 1991.
- U. Feige and L. Lovasz.
Two-prover one-round proof systems: their power and
their problems.
In STOC 92, 733-744, 1992.
- A. Shamir.
IP = PSPACE.
Journal of the ACM 39(4):869-877, 1992.
- A. Shen.
IP = PSPACE: simplified proof.
Journal of the ACM 39(4):878-880, 1992.
- A. Condon and R. Ladner.
Interactive proof systems with polynomially
bounded strategies.
Journal of Computer and System Sciences 50:506-518, 1995.
Interactive proofs and hardness of approximation:
- C. Papadimitriou and M. Yannakakis. Optimization, approximation and
complexity classes. Journal of Computer and System Sciences 43:425-440,
1991.
- L. Babai.
Interactive proofs and approximation.
In ISTCS 93, 266-274, 1993.
- C. Lund and M. Yannakakis.
On the hardness of approximating minimization
problems.
Journal of the ACM 41(5):960-981, 1994.
(reserved)
- M. Bellare and M. Sudan.
Improved non-approximability results.
In STOC 94, 184-193, 1994.
- U. Feige and J. Kilian.
Two prover protocols - low error at affordable
rates. In STOC 94, 172-183, 1994.
- U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy.
Interactive proofs and the hardness of
approximating cliques.
Journal of the ACM 43(2):268-292, 1996.
- S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy.
Proof verification and the hardness of
approximation problems.
Journal of the ACM 45(3):501-555, 1998.
- M. Bellare, O. Goldreich and M. Sudan.
Free bits, PCPs, and nonapproximability - towards
tight results.
SIAM Journal on Computing 27(3):804-915, 1998.
Interactive proofs and cryptography:
- M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson.
Multi-prover interactive proofs: how to
remove intractability assumptions.
In STOC 88, 113-131, 1988.
- O. Goldreich and E. Kushilevitz.
A perfect zero-knowledge proof for a problem
equivalent to discrete logarithm.
In Crypto 88, 1988.
- O. Goldreich, S. Micali, and A. Wigderson.
Proofs that yield nothing but their validity or
all languages in NP have zero-knowledge proof systems.
Journal of the ACM 38(1): 691-729, 1991.
- M. Ben-Or, O. Goldreich, S. Goldwasser, J. Hastad, J. Kilian, S. Micali
and P. Rogaway.
Everything provable is provable in
zero-knowledge.
In Crypto 88, 1988.
- D. Lapidot and A. Shamir.
A one-round, two-prover, zero-knowledge protocol for NP.
In Crypto 91, 1991.
- C. Dwork, U. Feige, J. Kilian, M. Naor, and S. Safra.
Low Communication, 2-prover zero-knowledge proofs for NP.
In Crypto 92, 217-229, 1992.
- U. Feige and J. Kilian.
Two prover protocols - low error at affordable
rates. In STOC 94, 172-183, 1994.
- R. Canetti, O. Goldreich, S. Goldwasser and S. Micali.
Resettable zero-knowledge.
In STOC 00, 235-244, 2000.