You are here: Home / Events / Workshops / Workshop: Complexity and Cryptography: Status of Impagliazzo’s Worlds

Workshop: Complexity and Cryptography: Status of Impagliazzo’s Worlds


russell.worlds.workshop {at} gmail(.)com

Workshop dates and place: June 3-5th, Princeton (following STOC 2009)

Organizers: Boaz Barak (Princeton University) and Salil Vadhan (Harvard University)

Joint effort of DIMACS and the Center for Computational Intractability

Tentative Program (including location, parking info)

Registration is now CLOSED if you’re interested in coming to the workshop, please email russell.worlds.workshop {at} gmail(.)com to see if there’s still room.

Everyone who registers should reserve a room at the Nassau Inn (see below).

This workshop’s goal is to bring together experts and discuss recent results and promising directions in the areas of average-case complexity and algorithms, hardness amplification, and basing cryptographic primitives on weaker or different assumptions.

More details, including tentative program and how to register, will be posted on this page later.

The workshop is a joint venture of DIMACS and the Center for Computational Intractability.

About the name: The name “Impagliazzo’s Worlds” refers to a 1995 survey by Russell Impagliazzo, in which he described the various possibilities for cryptography and average-case complexity of NP problems that are consistent with our current knowledge of complexity, and gave these possibilities evocative and memorable names.

Travel information:

  1. The workshop will start on 11am on Wednesday June 3,
    and end on 5pm on Friday June 5th.
  2. A block of rooms has been reserved at the Nassau Inn at
    the rate of $132 per day. To reserve a room you need to
    call them (800-862-7728 or 609-921-7500) and ask for
    the Cryptography Workshop room block (room block #12731).
  3. IMPORTANT ISSUE: because of commencement there is no
    room in Nassau Inn for the night of Tuesday June 2nd.
    We scheduled the workshop to start at 11am on Wednesday
    so that it will be possible for you to stay Tuesday in
    New York or in the STOC conference hotel in Bethesda.
    There is an Amtrak train leaving Washington DC (25
    minutes by Metro from conference hotel) at 8:10am on
    Wednesday and arriving to Trenton at 10:27am. If enough
    people take that train then we can arrange a shuttle to
    pick them up from Trenton to the talks.