Chercheurs

Informatique / COOK, STEPHEN A.

sacook

Position

Distinguished University Professor
Department of Computer Science
University of Toronto
Toronto, Canada

Thèmes de recherche

Dr. Cook is recognized internationally for providing a definition for \"efficiently computable\" and giving mathematical evidence for a number of problems which were unlikely to be efficiently computable.

He has made fundamental contributions in complexity theory, the design and analysis of algorithms, logic (notably proof complexity) and programming language semantics. His work is characterized by its creativity and pervasive influence throughout his distinguished 40 year career and he continues to produce seminal contributions on feasible logics and complexity theory.

Prix et récompenses

1982 - Turing Award
1984 - Membre de la Société royale du Canada
1997 - Prix Izaak-Walton-Killam
1999 - Prix CRM-Fields-PIMS
2005 - Prix d\'excellence du CRSNG

Publications

Theories for Subexponential-size Bounded-depth Frege Proofs. Kaveh Ghasemloo and Stephen A. Cook. Computer Science Logic (CSL) 2013. DOI: 10.4230/LIPIcs.CSL.2013.296 September, 2013.

The Complexity of the Comparator Circuit Value Problem. Stephen A. Cook, Yuval Filmus, and Dai Tri Man Le. arXiv:1208.2721v1 [] 13 Aug 2012. This paper is a sequel to the following paper: A Formal Theory for the Complexity Class Associated with the Stable Marriage Problem. Dai Tri Man Le, Stephen Cook, and Yuli Ye. CSL 2011 (Computer Science Logic).

Relativizing Small Complexity Classes and their Theories, Klaus Aehlig, Stephen Cook, and Phuong Nguyen. Manuscript pp 1--18, April, 2007 (submitted).

The Complexity of Proving the Discrete Jordan Curve Theorem, Phuong Nguyen and Stephen Cook. Accepted for LICS 2007.

Consequesnces of the Provability of NP subset P/poly, Stephen Cook and Jan Krajicek. Manuscript pp 1--27, August, 2006, Revised June, 2007, accepted for J.Symbolic Logic.

Comments on Beckmann\'s Uniform Reducts, Stephen Cook. arXiv manuscript January, 2006.

Computing over the Reals: Foundations for Scientific Computing, Mark Braverman and Stephen Cook. Notices of the AMS 53,3 (March 2006), pp 318--329.

A Note on the Lengths of G0 Proofs, Stephen Cook. Manuscript pp 1--3, December, 2004.

Theories for Complexity Classes and their Propositional Translations, Stephen Cook. In ``Complexity of computations and proofs\'\', Jan Krajicek, ed., Quaderni di Matematica, 2003, pp 175--227. (This volume appeared March, 2005.)

Quantified Propositional Calculus and a Second-Order Theory for NC1, Stephen Cook and Tsuyoshi Morioka. Archive for Mathematical Logic Vol 44 No. 6 (Aug 2005) pp 711-749.

The strength of replacement in weak arithmetic, Stephen Cook and Neil Thapen. Nineteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2004), pp 256--264.

A Second-Order Theory for NL, Stephen Cook and Antonina Kolokolova. Nineteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2004), pp 398--407.

Theories for TC0 and other Small Complexity Classes, Phuong Nguyen and Stephen Cook. LMCS 2,1 (2006) (Logical Methods in Computer Science) Special Issue: Selected Papers of LICS 2004.

The Proof Complexity of Linear Algebra, Michael Soltys and Stephen Cook. Annals of Pure and Applied Logic 130 (2004), 277-323.

The Importance of the P versus NP Question, Stephen Cook. JACM 50, 1, 2003 (50th Anniversary Issue), pp 27-29.

A Complete Axiomatization for Blocks World, Stephen Cook and Yongmei Liu. J. Logic Computat. Vol 13, No. 4 pp 581--594. A preliminary verions appears in Seventh International Symposium on Artificial Intelligence and Mathematics, January, 2002.

The Optimal Location of Replicas in a Network Using a READ-ONE-WRITE-ALL Policy, Stephen A. Cook, Jan Pachl, and Irwin Pressman. Distributed Computing (2002), 15: 57-66 (copyright Springer-Verlag).

A Second-order System for Polytime Reasoning Based on Gradel\'s Theorem, Stephen Cook and Antonina Kolokolova. APAL 124 (2003) 193-231. Click here for a preprint. An early version is in Proceedings Sixteenth Annual IEEE Symposium on Logic in Computer Science (LICS \'01) 2001, 177--186.

Efficiently Approximable Real-Valued Functions, Valentine Kabanets, Charles Rackoff, and Stephen A. Cook. ECCC Report No. 34(2000).

The P versus NP Problem, Stephen Cook, April, 2000. Manuscript prepared for the Clay Mathematics Institute for the Millennium Prize Problems (revised November, 2000).

The Relative Complexity of NP Search Problems (with Beame, Edmonds, Impagliazzo, and Pitassi). STOC 95.

Boolean Programs and Quantified Propositional Proof Systems (with Michael Soltys). Bulletin of the Section of Logic, University of Lodz, Department of Logic, Vol 28 No. 3 (1999) pp 119--129.

An Exponential Lower Bound for the Size of Monotone Real Circuits, Armin Haken and Stephen A. Cook. FOCS 95.

A Tight Relationship between Generic Oracles and Type-2 Complexity Theory (with Russell Impagliazzo and Tomoyuki Yamakami). Information and Computation 137,2, 1997, pp159-170.

Finding Hard Instances of the Satisfiability Problem: A Survey (with David Mitchell). DIMACS Series in Discrete Math. and Theoretical Computer Science,35, 1997, pp1-17.

Relating the Provable Collapse of P to NC1 and the Power of Logical Theories. DIMACS Series in Discrete Math. and Theoretical Computer Science, 39, 1998.

Review of three papers relating the collapse of the polynomial hierarchy to the collapse of bounded arithmetic.

Functional Interpretations of Feasibly Constructive Arithmetic, Stephen Cook and Alasdair Urquhart. Annals of Pure and Applied Logic 63 (1993) 103-200.

A New Recursion-Theoretic Characterization of the Polytime Functions (with Stephen Bellantoni). Computational Complexity 2 (1992), pp97-110.

Storage Requirements for Deterministic Polynomial Time Recognizable Languages (with Ravi Sethi). JCSS 13, 1, 1976.

The Complexity of Theorem Proving Procedures. Proceedings Third Annual ACM Symposium on Thoery of Computing, May 1971, pp 151-158.

Chapter III of my 1966 PhD thesis \"On the Minimum Computation Time of Functions\".