Friday - Saturday, May 12 - 13, 2023
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 conundrum.
Paul Beame
Lenore Blum
Manuel Blum
Cynthia Dwork
Leonid Levin (via zoom)
Michael Luby
Moni Naor
Avi Wigderson (via zoom)
Ryan Williams
Sam Buss
Marco Carmosino
Valentine Kabanets
Antonina Kolokolova
Toniann Pitassi
UC San Diego
Computer Science & Engineering Department