
Workshop on Interactive Proofs, PCP's and
Fundamentals Of Cryptography
Preliminary Schedule of Talks
Monday, May 11, 1998
08:30 – 9:30
 Registration 
09:30  10:20
 Johan Hastad, Royal Institute of Technology 
 "On Improving the Inapproximability Constant for Vertex Cover" 
10:20  10:50
 Coffee Break 
10:50  11:40
 Mario Szegedy, AT&T Research Laboratory 
 "Proof Systems with Promise" 
11:40  01:45
 Lunch 
01:45  02:35
 JinYi Cai, State University of New York, Buffalo 
 "A New Transference Theorem in the Geometry of Numbers and Applications
to Ajtai's Connection Factor" 
02:40  03:30
 Uriel Feige, Weizmann Institute of Science 
 "Making Games Short" 
03:30  04:00
 Afternoon Break 
04:00  04:50
 Salil Vadhan, Massachusetts Institute of Technology 
 "A Complete Problem for Statistical ZeroKnowledge" 
04:55  05:45
 Amit Sahai, Massachusetts Institute of Technology 
 "Honest Verifier Statistical ZeroKnowledge" 
 "Equals General Statistical Zero Knowledge" 
Tuesday May 12, 1998
09:30  10:20
 Silvio Micali, Massachusetts Institute of Technology 
 "Certified Email with Invisible Post Offices" 
10:20  10:50
 Coffee Break 
10:50  11:40
 Mihir Bellare, University of California, San Diego 
 "Plaintext Awareness, NonMalleability, and Chosen Ciphertext Security:
Implications and Separations" 
11:40  01:45
 Lunch 
01:45  02:35
 Moni Naor, Weizmann Institute of Science 
 "A Taxonomy of EncryptionScheme Security" 
2:40  03:30
 Ran Canette, IBM 
 "On Realizing Random Oracles" 
03:30  04:00
 Afternoon Break 
04:00  04:50
 Tal Malkin, Massachusetts Institute of Technology 
 "A Random Server Model for Private Information Retrieval" 
04:55  05:45
 Yuval Ishai, Massachusetts Institute of Technology 
 "Protecting Data Privacy in Private Information Retrieval Schemes" 
Wednesday May 13, 1998
09:30  10:20
 Shafi Goldwasser, Massachusetts Institute of Technology/Weizmann
Institute of Science 
 "On the Limits of NonApproximability of Lattice Problems" 
10:20  10:50
 Coffee Break 
10:50  11:40
 Daniele Micciancio, Massachusetts Institute of Technology 
 "The Shortest Vector Problem is NPhard to Approximate Within Some Constant
Factor" 
11:40  01:45
 Lunch 
01:45  02:35
 Oded Goldreich, Weizmann Institute of Science 
 "Combinatorial Property Testing: A Survey" 
02:40  03:30
 Ronitt Rubinfeld, Cornell University 
 "Spot Checking" 
03:30  04:00
 Afternoon Break 
04:00  04:50
 Madhu Sudan, Massachusetts Institute of Technology 
 "Reconstructing Polynomials from Noisy Data" 
04:55  05:45
 Hal Wasserman, University of California at Berkeley 
 "HighNoise Decoding for AlgebraicGeometric Codes" 
Thursday May 14, 1998
09:30  10:20
 Polar Bear Pete, Metro Toronto Zoo 
 "Some Open Questions in Cryptozoology" 
10:30  05:30
 Excursion to the Metro Toronto Zoo 
Friday May 15, 1998
09:30  10:20
 Claus Schnorr, Universität Frankfurt 
 "Security of Arbitrary RSA and of All Discrete Log Bits" 
10:20  10:50
 Coffee Break 
10:50  11:40
 Omer Reingold, Weizmann Institute of Science 
 "PseudoRandom Functions and Their Relaxation" 
11:40  01:45
 Lunch 
01:45  02:35
 Shmuel Safra, TelAviv University 
 "Towards Optimal PCP Characterizations of NP" 
02:40  03:30
 Venkatesan Guruswami, Massachusetts Institute of Technology 
 "The Strength of Adaptive Queries in Probabilistically Checkable Proofs" 
03:30  04:00
 Afternoon Break 
04:00  04:50
 Luca Trevisan, Massachusetts Institute of Technology 
 "Recycling Queries in Probabilistically Checkable Proofs" 
04:55  05:45
 TBA 

