Symposium on 50 Years of Complexity Theory: A Celebration of the Work of Stephen Cook

May 6 - 9, 2019, The Fields Institute

Location: Fields Institute, Room 230

Description

This symposium celebrates 50 years of NP-Completeness and the outstanding achievements of Stephen Cook and his remarkable influence on the field of computing.

Join us on Monday, May 6th to kick off the symposium with a Public Event featuring a talk by Christos Papadimitriou (Columbia University) at the JJR Macleod Auditorium (Room MS 2158), Medical Sciences Building, University of Toronto, 1 King's College Circle starting at 7pm - REGISTER separately for your free Christos Papadimitriou event ticket here!

Talks will be broadcast live online whenever possible.

Schedule

Monday, May 6th, 2019
19:00 to 21:00	The Story of Complexity Christos Papadimitriou, Columbia University Location:Medical Sciences Auditorium, University of Toronto
21:00 to 23:00	Reception at the Fields Institute

Tuesday, May 7th, 2019
08:50 to 09:00	Welcome
09:00 to 09:50	Computational Complexity in Theory and Practice Richard Karp, University of California Berkeley
09:50 to 10:20	Coffee break
10:20 to 11:10	Fine-grained completeness for first-order logic and extensions Russell Impagliazzo, University of California, San Diego
11:10 to 12:00	Computability and complexity of Julia sets Mark Braverman, Princeton University
12:00 to 13:30	Lunch
13:30 to 14:20	Complexity, Optimization and Math (or, Can we prove that P != NP by gradient descent?) Avi Wigderson, Institute for Advanced Study, Princeton
14:20 to 15:10	NP-Completeness and its Algebraic Siblings Leslie Valiant, Harvard University
15:10 to 15:40	Coffee break
15:40 to 16:10	The Tree Evaluation Problem James Cook, Google
16:10 to 17:00	Can Model Theory Separate NP from co-NP? Ronald Fagin, IBM Almaden Research Center

Wednesday, May 8th, 2019
09:00 to 09:50	Adventures in Complexity Michael Sipser, Massachusetts Institute of Technology
09:50 to 10:20	Coffee break
10:20 to 11:10	On hierarchies Rahul Santhanam, University of Oxford
11:10 to 12:00	Propositional proofs and monotone computations Pavel Pudlák, Institute of Mathematics, Czech Academy of Sciences
12:00 to 13:30	Lunch
13:30 to 14:20	Groups and Individuals in Fairness and Probability (work in progress) Cynthia Dwork, Harvard University
14:20 to 15:10	Logical foundations of complexity theory Jan Krajíček, Charles University
15:10 to 15:40	Coffee break
15:40 to 16:30	Algorithms, Proofs, and Communication: A Unified Perspective Robert Robere, DIMACS
16:30 to 17:00	Subrecursion, P and NP Bruce Kapron, University of Victoria
18:00 to 22:00	Banquet in Honour of Stephen Cook - Great Hall, Hart House, University of Toronto

Thursday, May 9th, 2019
09:00 to 09:50	P, NP and Proof Complexity Alexander Razborov, University of Chicago
09:50 to 10:20	Coffee break
10:20 to 11:10	NP-complete Problems and Physics Scott Aaronson, University of Texas at Austin
11:10 to 13:30	Student Round Table Lunch with Stephen Cook
13:30 to 14:00	BREAK
14:00 to 14:50	Factoring and bounded arithmetic Emil Jeřábek, Czech Academy of Sciences
14:50 to 15:40	NP and some nice polytopes Jack Edmonds

Event Sponsors

Travel funding

Students are encouraged to apply for travel funding here.

In the News

The Symposium on 50 Years of Complexity Theory: A Celebration of the Work of Stephen Cook was featured in the University of Toronto Arts & Science News website on June 11, 2019. The article, written by Chris Sasaki, describes Professor Stephen's Cook's impressive career in complexity theory and how this inspired the symposium held at Fields.

Read the full article here.

Registered Participants

Name	Affiliation
Scott Aaronson	University of Texas at Austin
Sepehr Abbasi Zadeh	University of Toronto
James Abello	Rutgers University
Deeksha Adil	University of Toronto
Rishav Agarwal	University of Waterloo
Sushant Agarwal	University of Waterloo
Zachary Alexander	University of Toronto
Jurgen Aliaj	University of Toronto
Nivasini Ananthakrishnan	University of Waterloo
Hassan Ashtiani	McMaster University
Aseem Baranwal	University of Waterloo
Paul Beame	University of Washington
Majid Beheshti Mohtasham	Memorial University
Steve Bellantoni	TD
Shai Ben-David	University of Waterloo
Ryan Berryhill	University of Toronto
Leopoldo Bertossi	Carleton University
Manuel Blum	Carnegie Mellon University
Allan Borodin	University of Toronto
Judy Borodin
Mark Braverman	Princeton University
Anne Broadbent	University of Ottawa
Kayman Brusse	University of Toronto
Andrei Bulatov	Simon Fraser University
Sam Buss	Univ. of California, San Diego
Kathie Cameron	Wilfrid Laurier University
Alex Cann	University of Toronto
Tim Capes
Bruno Cavalar	University of São Paulo and University of Toronto
Eddie Cheng	Oakland University
Christina Christara	University of Toronto
James Cook	Google
Stephen Cook	University of Toronto
Barbara Corneil	University of Toronto
Derek Corneil	University of Toronto
Elliot Creager	University of Toronto
David Cui	University of Toronto
Jian Cui	University of Toronto
Sven Dickinson	Samsung and University of Toronto
Sally Dong	University of Washington
Titus Dose	Universität Würzburg
Cynthia Dwork	Harvard University
Jack Edmonds
Jeff Edmonds	York University
Faith Ellen	University of Toronto
Jesse Elliott	University of Waterloo
Patricia Evans	University of New Brunswick
Ronald Fagin	IBM Almaden Research Center
Yuval Filmus	Technion
David Fleet	University of Toronto
Noah Fleming	University of Toronto
Lila Fontes	Swarthmore College
Martin Fürer	The Pennsylvania State University
Vijay Ganesh	University of Waterloo
Daya Gaur	University of Lethbridge
Kaveh Ghasemloo	Google
Soumik Ghosh	University of Waterloo
Garth Gibson	Vector Institute
Stephen Gismondi	University of Guelph
Christian Glasser	University at Wuerzburg
Shafi Goldwasser	Simons Institute, UC Berkeley, MIT
Mika Göös	IAS
Gosta Grahne	Concordia University
Laura Graves	Memorial Institute of Newfoundland
Chaowen Guan	University at Buffalo
Xiangyu Guo	State University of New York at Buffalo
Arvind Gupta	University of Toronto and The Fields Institute
Vassos Hadzilacos	University of Toronto
Ian Hambleton	The Fields Institute
Clovis Hamel	University of Toronto
Mingrui Han	University of Toronto
Nathan Harms	University of Waterloo
Eugene Hayden	University of Waterloo
Mu He	Western University
Kevan Hollbach	University of Toronto
H. James Hoover	University of Alberta
Safwan Hossain	University of Toronto
Samuel Huang	Google
Andrew Hughes	State University of New York at Buffalo
Russell Impagliazzo	University of California, San Diego
Aditya Jayaprakash	University of Waterloo
Emil Jeřábek	Czech Academy of Sciences
Shalmali Joshi	Vector Institute
Valentine Kabanets	SFU
Erich Kaltofen	NCSU
Georges Kanaan	University of Toronto
Bruce Kapron	University of Victoria
Christodoulos Karavasilis	University of Toronto
Richard Karp	University of California Berkeley
Matthew Katzman	University of Oxford
Henry Kautz	NSF
Amir H. Khasahmadi	University of Toronto
Jordan Kilfoy	Toronto Metropolitan University
Valerie King	University of Victoria
David Kirkpatrick	University of British Columbia
Toryn Klassen	University of Toronto
Jeremy Ko	University of Toronto
Antonina Kolokolova	Memorial University
Jan Krajíček	Charles University
Simeon Krastnikov	University of Toronto
Mrinal Kumar	University of Toronto
Kyros Kutulakos	University of Toronto
David Landsman	University of Toronto
David Ledvinka	University of Toronto
Chunxiao Li	University of Waterloo
David Liu	University of Toronto
Shi Hao Liu	University of Toronto
Xinyuan Li	University of Toronto
Yaqiao Li	McGill University
Sébastien Lord	University of Ottawa
Anna Lubiw	University of Waterloo
Jonathan Lung	Kepler Communications
Yossi Luzon	University of Toronto
Yasaman Mahdaviyeh	University of Toronto
Farzaneh Mahdisoltani	University of Toronto
Kenzy Malek	Concordia University
Sai Vikneshwar Mani Jayaraman	University at Buffalo
Henrique Matulis	University of Toronto
Cameron McCarthy	Western University
Sheila McIlraith	University of Toronto
Pierre McKenzie	Université de Montréal
Venkatesh Medabalimi	University of Toronto
Maryam Mehri Dehnavi	University of Toronto
Sanketh Menda	University of Waterloo
Fanwang Meng	McMaster University
Ian Mertz	University of Toronto
Paraskevi Micha	University of Toronto
David Mitchell	Simon Fraser University
Ali Moallemi	Concordia University
Mina Mohammadian	Australian National University
Michael Molloy	University of Toronto
Tsuyoshi Morioka	Kanagawa Global IT Research
Colin Morris
Lalla Mouatadid	University of Toronto
Sasank Mouli	University of California at San Diego
Seyyed Ramin Mousavi Haji	University of Alberta
Hamoon Mousavi	University of Toronto
Ian Munro	University of Waterloo
Mohammad Nasirifar	University of Toronto
Ashwin Nayak	University of Waterloo
Azin Nazari	University of Waterloo
Seyed Sajjad Nezhadi	University of Toronto
Phuong Nguyen	LiquidAnalytics
Oleksii Omelchenko	Simon Fraser University
Nnamdi Ozah	Memorial University
Christos Papadimitriou	Columbia University
Alex Parmentier	University of Waterloo
Kanstantsin Pashkovich	University of Ottawa
Miles Pitassi	University of Toronto
Toni Pitassi	University of Toronto
Supartha Podder	University of Ottawa
Pavel Pudlák	Institute of Mathematics, Czech Academy of Sciences
Ke Qiu	Brock University
Charles Rackoff	University of Toronto
Javad Rahimipour Anaraki	Memorial University
Akash Rakheja	University of Toronto
Jankie Ramsook	University of Toronto
Timothy Randolph	Columbia University
Sumeet Ranka	University of Toronto
Gautam Rayaprolu	McGill University
Alexander Razborov	University of Chicago
Kenneth Regan	University at Buffalo (SUNY)
Rüdiger Reischuk	ITCS Univ. Lübeck
Samin Riasat	University of Waterloo
Robert Robere	DIMACS
Siobhan Roberts
Peter Robinson	McMaster University
Arnold Rosenbloom	University of Toronto
Benjamin Rossman	University of Toronto
Daniel Roy	University of Toronto
Eric Ruppert	York University
Sushant Sachdeva	University of Toronto
Rahul Santhanam	University of Oxford
Joe Sawada	University of Guelph
Joseph Scott	University of Waterloo
Alan Selman	University at Buffalo
Bart Selman	Cornell University
Sharon Selman	University at Buffalo
Rik Sengupta	University of Massachusetts - Amherst
Nisarg Shah	University of Toronto
Jeffrey Shallit	University of Waterloo
Ilya Shapirovsky	Russian Academy of Sciences
Ekansh Sharma	University of Toronto
Zhendong Sha	Memorial University
Adrian She	University of Toronto
Morgan Shirley	University of Toronto
Nikki Sigurdson	University of Toronto
Michael Sipser	Massachusetts Institute of Technology
Alan Skelley	Google
Dmitry Sokolov	KTH Royal Institute of Technology
Roberto Solis-Oba	Western University
Stephen Solis	Western University
Michael Soltys	California State University Channel Islands
Suzanne Stevenson	University of Toronto
Tyrone Strangway	University of Toronto
Mark Stuart	not applicable
Mashbat Suzuki	McGill University
Siddharth Swain	Qualcomm
Stefan Szeider	TU Vienna, Austria
Franklin Tall	University of Toronto
Eugenia Ternovska	Simon Fraser University
Denis Therien	Element AI
Sam Toueg	University of Toronto
Aleksander Trajcevski	Toronto Metropolitan University
Stavros Tsogkas
Jamie Tucker-Foltz	Amherst College
Iddo Tzameret	Royal Holloway, University of London
Esko Ukkonen	University of Helsinki
Alasdair Urquhart	University of Toronto
Leslie Valiant	Harvard University
Thomas Vandeven	Western University
Andreas Veneris	University of Toronto
Felipe Vicencio-Heap	University of Toronto
Michelle Waitzman	Writer
Di Wang	SUNY at Buffalo
Stephen M. Watt	University of Waterloo
Avi Wigderson	Institute for Advanced Study, Princeton
Nils Wilde	University of Waterloo
Jinjin Wu	University of Toronto
Shelley Wu	University of Waterloo
Qiqi Xu	University of Toronto
Rupei Xu	University of Texas at Dallas
Henry Yuen	University of Toronto
cole Zemel	University of Toronto
Richard Zemel	University of Toronto
Beibei Zhang	University of Toronto
Stanley Zhang	University of Toronto
Martin Ziegler	KAIST