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 non-interactive 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, Non-Malleability, and Chosen Ciphertext Security: Implications and Separations"

  
  
• Jin-Yi 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 Non-Approximability 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 E-mail with Invisible Postoffices"

  
  
• Daniele Micciancio, Massachusetts Institute of Technology
  

  "The Shortest Vector Problem is NP-hard to Approximate Within Some Constant Factor"

• Moni Naor, Weizmann Institute of Science
  

  "A Taxonomy of Encryption-Scheme Security"

  
  
• Omer Reingold, Weizmann Institute for Science
  

  "Pseudo-Random Functions and their Relaxation"

  
  
• Ronitt Rubinfeld, Cornell University
  

  "Spot Checking"

  
  
• Amit Sahai, Massachusetts Institute of Technology
  

  "Honest Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge"

  
  
• 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 Zero-Knowledge"

  
  
• Hal Wasserman, University of California, Berkeley
  

  "High-Noise Decoding for Algebraic-Geometric 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

Jin-Yi 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, Tel-Aviv 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