DIMACS Workshop on Complexity and Cryptography: Status of Impagliazzo's Worlds

June 3 - 5, 2009
Princeton University

Organizers:

Boaz Barak, Princeton University, boaz at CS.Princeton.edu

Salil Vadhan, Harvard University, salil at eecs.harvard.edu

Workshop Program:

Computational Intractability website: http://intractability.princeton.edu/programs/complexity-crypto-workshop/

This is a preliminary program.

Wednesday June 3, 2009

10:30 - 11:00  Breakfast

11:00 - 11:15  Opening words

11:15 - 12:15  Five Worlds of Problems
               Russell Impagliazzo

12:30 -  2:30  Lunch

 2:30 -  3:30  Public-Key Cryptosystems Based from the Worst-Case Shortest Vector Problem
               Chris Peikert

 3:30 -  4:00  Coffee break

 4:00 -  5:00  A Homomorphic Public Key Cryptosystem
               Craig Gentry

 6:00 -  9:00  Banquet at Palmer House

Thursday, June 4, 2009

 9:00 -  9:30  Breakfast

 9:30 - 10:30  Inaccessible Entropy
               Iftach Haitner

10:30 - 11:00  Coffee break

11:00 - 12:00  Luca Trevisan: On Algorithmica vs Heuristica

12:00 -  1:30  Lunch

 1:30 -  2:30  Algorithmic Phase Transitions in Constraint Satisfaction Problems
               Dimitris Achlioptas

 2:30 -  3:30  Uri Feige: Dense subgraphs of random graphs

 3:30 -  4:00  Coffee Break

 4:00 -  5:00  Cryptography from Average-Case Hardness
               Benny Applebaum

 5:00 -  7:00  Dinner on your own.

 7:00 -  9:00  Rump/open problems  session

Friday, June 5, 2009

 9:00 -  9:30  Breakfast

 9:30 - 10:30  Scott Aaronson:  Impagliazzo's Worlds in Arithmetic Complexity

10:30 - 11:00  Coffee break

11:00 - 12:00  Valentine Kabanets: Direct Product Testing

12:00 -  1:30  Lunch

 1:30 -  2:30  CHow Fair Can a Coin Toss Be?
               Moni Naor

 2:30 -  3:30  Efficiency vs. assumptions in secure computation
               Yuval Ishai 

 3:30 -  4:00  Coffee break

 4:00 -  5:00  A New Paradigm for Constructing Secure Protocols
               Amit Sahai

Previous: Participation

Workshop Index

DIMACS Homepage