jf@RESEARCH.ATT.COM (Joan Feigenbaum) (11/02/90)
DIMACS is holding a workshop on structural complexity
and cryptography under the rubic of the Special Year on the
Complexity of Interactive Computation. The workshop chairs
are Eric Allender (Rutgers), Jin-yi Cai (Princeton), and
Joan Feigenbaum (AT&T Bell Labs). The program for the workshop
is attached. Talk abstracts are available from Joan
(jf@research.att.com). Local arrangements information is
available from Eric (allender@cs.rutgers.edu).
Further announcements will be sent to the DIMACS mailing list.
If you are not on this list but would like to be, contact
Ida Castellano (ida@dimacs.rutgers.edu).
===============================================================
DIMACS WORKSHOP ON STRUCTURAL COMPLEXITY AND CRYPTOGRAPHY
Rutgers University, December 1990
===============================================================
Monday, Dec. 3
9:45 - 10:30 Feigenbaum: Overview of Locally Random Reductions
and their Relationship to IP and Checkers
10:45 - 11:30 Fortnow: On the Random-Self-Reducibility of Complete Sets
11:45 - 12:30 Yao: An Application of Communication Complexity to
Cryptography
12:30 - 2:00 LUNCH
2:00 - 3:00 Levin: Intractability of Random NP Instances: An Overview
3:30 - 4:30 Impagliazzo: Open Problems in the Theory of Average-Case
Complexity
4:30 - ????? Discussion and Open Problems
===============================================================
Tuesday, Dec. 4
9:45 - 10:30 Lund: Interactive Proof Systems and Alternating
Time-Space Complexity
10:45 - 11:30 Shamir: Parallel Two Prover Zero Knowledge Protocols
11:45 - 12:30 Ostrovsky: Properties of Statistical Zero Knowledge
12:30 - 2:00 LUNCH
2:00 - 2:45 Beigel: Improved Bounds on Coherence and Checkability
3:00 - 3:45 Evans: Checking the Correctness of Memories
4:00 - 4:45 Blum: Breaking the Complexity Barrier with Waffling Programs
4:45 - 6:00 Discussion and Open Problems
6:00 - 8:00 Wine and Cheese Reception
===============================================================
Wednesday, Dec. 5
9:45 - 10:30 Condon: The Complexity of Stochastic Games
10:45 - 11:30 Fischer: Flipping a Coin Among Friends
11:45 - 12:30 Beck: A Las Vegas Version of the Lovasz Local Lemma
12:30 - 2:00 LUNCH
Afternoon: Rump Session and/or play hooky
===============================================================
Thursday, Dec. 6
9:45 - 10:30 Selman: One-way Functions in Complexity Theory
10:45 - 11:30 Watanabe: Structural Analysis of the Complexity of
Inverse Functions
11:45 - 12:30 Wang: On Isomorphism Problems in E
12:30 - 2:00 LUNCH
2:00 - 3:00 Lutz: Intrisically Pseudorandom Sequences
3:30 - 4:15 Bellare: Trading Interaction for Randomness: Speedup
at Logarithmic Cost