
Complexity Theory Program
Workshop on Interactive Proofs, PCP's
and Fundamentals of Cryptography
May 11 May 15, 1998
Topics will include recent results in interactive and noninteractive
proofs,
as well as new results about the fundamentals of cryptography.
Schedule of Talks
Organizing Committee:
S. Goldwasser, Massachusetts Institute of Technology
C. Rackoff, University of Toronto
Partial List of Invited Speakers
 Mihir Bellare, University of California, San Diego
 "Plaintext Awareness, NonMalleability, and Chosen Ciphertext Security:
Implications and Separations"
 JinYi Cai, University of Buffalo
 "A New Transference Theorem In the Geometry of Numbers and applications
to Ajtai's Connection Factor"
 Ran Canetti, IBM
 "On Realizing Random Oracles"
 Uriel Feige, Weizmann Institute of Science
 "Making Games Short"
 Oded Goldreich, Weizmann Institute of Science
 "Combinatorial Property Testing (a survey)"
 Shafi Goldwasser, Massachusetts Institute of Technology/Weizmann Institute
of Science
 "On the Limits of NonApproximability of Lattice Problems"
 Venkatesan Guruswami, Massachusetts Institute of Technology
 "The Strength of Adaptive Queries in Probabilistically Checkable Proofs"
 Johan Hastad, Royal Institute of Technology
 "On Improving the Inapproximability Constant For Vertex Cover"
 Tal Malkin, Massachusetts Institute of Technology
 "A Random Server Model for Private Information Retrieval"
 "Protecting Data Privacy in Private Information Retrieval Schemes"
 Silvio Micali, Massachusetts Institute of Technology
 "Certified Email with Invisible Postoffices"
 Daniele Micciancio, Massachusetts Institute of Technology
 "The Shortest Vector Problem is NPhard to Approximate Within Some
Constant Factor"
 Moni Naor, Weizmann Institute of Science
 "A Taxonomy of EncryptionScheme Security"
 Omer Reingold, Weizmann Institute for Science
 "PseudoRandom Functions and their Relaxation"
 Ronitt Rubinfeld, Cornell University
 "Spot Checking"
 Amit Sahai, Massachusetts Institute of Technology
 "Honest Verifier Statistical ZeroKnowledge Equals General Statistical
ZeroKnowledge"
 Claus Schnorr, Universitat Frankfurt
 "Security of Arbitrary RSA and of "All" Discrete Log Bits"
 Madhu Sudan, Massachusetts Institute of Technology
 "Reconstructing Polynomials from Noisy Data"
 Nario Szegedy, AT&T Reserarch Laboratories
 "Proof Systems with Promise"
 Luca Trevisan, Massachusetts Institute of Technology
 "Recycling Queries in Probabilistic Checkable Proofs"
 Salil Vadhan, Massachusetts Institute of Technology
 "A Complete Problem for Statistical ZeroKnowledge"
 Hal Wasserman, University of California, Berkeley
 "HighNoise Decoding for AlgebraicGeometric Codes"
Participants
 Micah Adler, University of Toronto
 Pavan Aduri, University of Buffalo
 Sanjeev Arora, Princeton University
 Tugkan Batu, Cornell University
 Mihir Bellare, University of California, San Diego
 JinYi Cai, University of Buffalo
 Ran Canetti, IBM
 Henry Cohn, Harvard University
 Yevgeniy Dodis, Massachusetts Institute of Technology
 Uriel Feige, Weizmann Institute of Science
 Oded Goldreich, Weizmann Institute of Science
 Shafi Goldwasser, Massachusetts Institute of Technology
 Venkatesan Guruswami, Massachusetts Institute of Technology
 Johan Hastad, Royal Institute of Technology
 Russell Impagliazzo, University of California, San Diego
 Yuval Ishai, Technion  Israel Institute of Technology
 Sanjeev Khanna, Bell Labs
 Adam Klivans, Massachusetts Institute of Technology
 Robert Krauthgamer, Weizmann Institute of Science
 Daniel Lewin, Massachusetts Institute of Technology
 Tal Malkin, Massachusetts Institute of Technology
 Silvio Micali, Massachusetts Institute of Technology
 Daniele Micciancio, Massachusetts Institute of Technology
 Steve Myers, University of Toronto
 Moni Naor, Weizmann Institute of Science
 Rafail Ostrovsky, Bell Communications Research
 Charles Rackoff, University of Toronto
 Ran Raz, Weizmann Institute of Science
 Omer Reingold, Weizmann Institute of Science
 Adi Rosen, University of Toronto
 Ronitt Rubinfeld, Cornell University
 Shmuel Safra, TelAviv University
 Amit Sahai, Massachusetts Institute of Technology
 Claus Schnorr, Universitat Frankfurt
 Alan Selman, University of Buffalo
 Samik Sengupta, State University of New York at Buffalo
 Madhu Sudan, Massachusetts Institute of Technology
 Mario Szegedy, ATT Research
 Luca Trevisan, Massachusetts Institute of Technology
 Salil Vadhan, Massachusetts Institute of Technology
 Patrick White, Cornell University

