[Proof Complexity] Workshop - Wrestling with Complexity and 5-Worlds Conundrum

Samuel Buss sbuss at ucsd.edu
Thu Apr 13 15:43:59 CEST 2023

Workshop announcement -- Call for participation

Wrestling with Complexity and the Five-Worlds Conundrum
Friday May 12 – Saturday May 13, 2023
U.C. San Diego

The so-called five-worlds of complexity were introduced by Russell
Impagliazzo (Fig. 1) to delineate five possible outcomes of the P
versus NP problem, ranging from the possibility that P is equal to NP
to the possibility that strong public-key cryptography is possible.
Questions about which world we live in are of central importance to
theoretical computer science. This workshop will address research into
topics in computational complexity, cryptographic assumptions,
randomness in computation, machine learning, complexity of proofs, and
related topics that address issues raised by the five worlds

The workshop is being held on the occasion of Russell Impagliazzo's
60th Birthday.

To be added to the mailing list for the workshop, please fill out the
google form at https://forms.gle/D8f5FCU22ZYJHYrV7. For more local
arrangements information, see the workshop webpage at
A workshop registration page will be available soon, as well as a
registration page for the workshop banquet (subject to space

Confirmed speakers:
 * Paul Beame
 * Lenore Blum
 * Manuel Blum
 * Sam Buss
 * Marco Carmosino
 * Cynthia Dwork
 * Valentine Kabanets
 * Antonina Kolokolova
 * Leonid Levin (via Zoom)
 * Michael Luby
 * Moni Naor
 * Toni Pitassi
 * Avi Wigderson (via Zoom)
 * Ryan Williams

Organizing committee:
Sam Buss, Marco Carmosino, Antonina Kolokolova, Valentine Kabanets,
and Toni Pitassi

More information about the Proof-Complexity mailing list