FEATURE
50 Years of Complexity Theory:
Celebrating the Work of Stephen Cook
May 6-9, 2019 • Fields Institute
Organizers: Allan Borodin, Arvind Gupta, and
Toniann Pitassi (University of Toronto)
Professor Stephen Cook’s foundational work in complexity theory
has had profound consequences not only for computer science,
but for nearly all areas of science. Cook’s illustrious career and
spectacular influence was the focus of a celebration that gathered
some of the world’s top theoretical computer scientists. This four-day
symposium explored Cook's work, recounted his breakthrough results
in complexity theory, feasible computation and bounded arithmetic,
and examined his influence on the field of computing. It is difficult
to point to any aspect of modern computational science which have
not been significantly impacted by Cook's work. In fact, there is
increasing recognition that his work has impact across all sciences.
Cook's formulation of NP-completeness raised the still-open question
of whether P = NP. This is one of the most significant mathematical
or computational open problems and one of the seven Clay
Mathematics Institute Millennium Prize Problems, which carries a
$1M prize for the first correct solution. The scientific program brought
together the world's top researchers in complexity theory and proof
complexity as well as researchers in other areas of application.
The symposium kicked off with a public lecture by Christos Papadimitriou
(Columbia University), on The Story of Complexity, where he gave a
history and exploration of complexity theory dating back to its roots
in logic. The three-day scientific program featured plenary talks by a
collection of distinguished scientists, including several Turing Award, Rolf
Nevanlinna Prize and Gödel Prize winners, and former students of Cook's:
Richard Karp (University of California, Berkeley, Turing Award, John von
Neumann Theory Prize), Leslie Valiant (Harvard University, Turing Award,
Rolf Nevanlinna Prize), Avi Wigderson (Institute for Advanced Study
[IAS], Rolf Nevalinna Prize, Gödel Prize), Alexander Razborov (University
of Chicago, Rolf Nevalinna Prize, Gödel Prize), Cynthia Dwork (Gödel
Prize), Jack Edmonds (John von Neumann Theory Prize), Scott Aaronson
(University of Texas), Russell Impagliazzo (University of California, San
Diego), Rahul Santhanam (Oxford University), Mark Braverman (Princeton
University), Bruce Kapron (University of Victoria), Robert Robere (IAS),
James Cook (Google), Ronald Fagin (IBM Almaden, Gödel Prize), Michael
Sipser (MIT), Pavel Pudlák (Czech Academy of Sciences), Jan Krajíček
(Charles University), and Emil Jeřábek (Czech Academy of Sciences).
The symposium also included a student luncheon hosted by Cook, and
an evening banquet in the Great Hall at the U of T's Hart House.
10