SCIENTIFIC PROGRAMS AND ACTIVITIES

November 13, 2018

A Workshop in Honour of Stephen A. COOK
"Steve Cook at 60" -- April 28 - 29, 2000


Stephen Cook was born in Buffalo, New York. He received his B.Sc. degree from the University of Michigan in 1961 and his SM and PhD degrees from Harvard University in 1962 and 1966 respectively. From 1966 to 1970 he was an Assistant Professor at the University of California, Berkeley. He joined the University of Toronto in 1970 as an Associate Professor and was promoted to a Professor in 1975.

Dr. Cook's principal research area is computational complexity, with excursions into programming language semantics, parallel computation and especially the interaction between logic and complexity theory. He has authored over 50 research papers, including his famous 1971 paper, "The Complexity of Theorem Proving Procedures", which introduced the theory of NP completeness. Dr. Cook was the 1982 recipient of the Turing award, a Killam Research Fellowship in 1982, and a Steacie Fellowship in 1977. He received computer science teaching awards in 1989 and 1995. He is a fellow of the Royal Society of Canada and was elected to membership in the National Academy of Sciences (U.S.) and the American Academy of Arts and Sciences.

List of Invited Participants

Allan Borodin, Organizer, University of Toronto
Paul Beame, University of Washington
Stephen J. Bellantoni, Scotia Capital Inc.
Daniel Brand, T.J. Watson Research Center, IBM
Sam Buss, University of California, San Diego
Alan Cobham, Weslyan University
Patrick Dymond, York University
Arvind Gupta, Simon Fraser University
Jim Hoover, University of Alberta
Russell Impagliazzo, University of California, San Diego
Valentine Kabanets, University of Toronto
Bruce Kapron, University of Victoria
Jan Krajicek, Academy of Sciences, Prague
Anna Lubiw, University of Waterloo
Pierre McKenzie, University of Montreal
Silvio Micali, Massachusetts Institute of Technology
Nicholas Pippenger, University of British Columbia
Toniann Pitassi, University of Arizona
Bob Reckhow, Zyqux
Steven Rudich, Carnegie Mellon University
Walter Savitch, University of California, San Diego
Iannis Tourlakis, University of Toronto
Les Valiant, Harvard University
Avi Wigderson, IAS & The Hebrew University
Tomoyuki Yamakami, University of Ottawa

Speakers

Paul Beame, University of Washington
"Superlinear time-space tradeoff lower bounds for randomized computation"

Stephen J. Bellantoni, Scotia Capital Inc.
"Diagonalizing NC along the delta axis"

Sam Buss, University of California, San Diego
"Ordinal Notations and Well-Orderings in Bounded Arithmetic"

Daniel Brand, T.J. Watson Research Center, IBM
"Theorem proving for software analysis"

Russell Impagliazzo, University of California, San Diego
"Which Problems have Strongly Exponential Complexity?"

Valentine Kabanets, University of Toronto
"Circuit Minimization Problem"

Bruce Kapron, University of Victoria
"An Induction Principle for Computational Indistinguishability"

Jan Krajicek, Academy of Sciences, Prague
"Tautologies from pseudo-random generators, AC^0 cardinality, and other bounded arithmetic"

Silvio Micali, Massachusetts Institute of Technology

Nicholas Pippenger, University of British Columbia
"Quantum Circuits"

Toniann Pitassi, University of Arizona
"A New Proof of the Weak Pigeonhole Principle"

Steven Rudich, Carnegie Mellon University
"A High Level Summary of Approaches for the P Versus NP Question"

Iannis Tourlakis, University of Toronto
"Time-space tradeoffs for SAT on non-uniform machines"

Les Valiant, Harvard University
"Robust Logic"

Avi Wigderson, IAS & The Hebrew University
"Pseudorandom Generators in Propositional Proof Complexity"

Tomoyuki Yamakami, University of Ottawa
"A Computational Approach Toward Realistic Quantum Logic"