Mathematician:Stephen Arthur Cook

Mathematician

American mathematician and computer scientist who has made considerable progress in the field of complexity theory.

Nationality

American

History

• Born: 14 Dec 1939, Buffalo, New York, USA
• 1961: Bachelor's degree from University of Michigan
• 1962: Master's degree from Harvard University
• 1966: Ph.D. from Harvard University
• 1966 - 1970: Assistant Professor at University of California, Berkeley
• 1970: Denied reappointment at Berkeley, joined University of Toronto as Associate Professor in the Computer Science and Mathematics departments
• 1975: Promoted to Professor
• 1977: Awarded a Steacie Fellowship
• 1982: Received the Turing award
• 1982: Awarded a Killam Research Fellowship
• 1985: Promoted to University Professor
• 1999: Received the CRM-Fields-PIMS prize

Theorems and Definitions

• Cook-Levin Theorem (independently of Leonid Anatolievich Levin)
• Cook Reduction

Results named for Stephen Arthur Cook can be found here.

Publications

• 1971: The Complexity of Theorem-Proving Procedures (STOC Ser. '71 : pp. 151 – 158) (in which Cook-Levin Theorem is presented)
• 1975: Feasibly Constructive Proofs and the Propositional Calculus
• 1979: The Relative Efficiency of Propositional Proof Systems (with Robert A. Reckhow)

• Logical Foundations of Proof Complexity (with Phuong The Nguyen)