The Solvability of the Derivability Problem for One-Normal Systems. - Stephen A. Cook (J. ACM, 1966)

Variations on Pushdown Machines (Detailed Abstract) - Stephen A. Cook (STOC, 1969)

Path Systems and Language Recognition - Stephen A. Cook (STOC, 1970)

Linear Time Simulation of Deterministic Two-Way Pushdown Automata. - Stephen A. Cook (IFIP Congress (1), 1971)

The Complexity of Theorem-Proving Procedures - Stephen A. Cook (STOC, 1971)

Characterizations of Pushdown Machines in Terms of Time-Bounded Computers. - Stephen A. Cook (J. ACM, 1971)

A Hierarchy for Nondeterministic Time Complexity. - Stephen A. Cook (J. Comput. Syst. Sci., 1973)

Time Bounded Random Access Machines. - Stephen A. Cook; Robert A. Reckhow (J. Comput. Syst. Sci., 1973)

On the Number of Additions to Compute Specific Polynomials (Preliminary Version) - Allan Borodin; Stephen A. Cook (STOC, 1974)

On the Lengths of Proofs in the Propositional Calculus (Preliminary Version) - Stephen A. Cook; Robert A. Reckhow (STOC, 1974)

An Observation on Time-Storage Trade Off. - Stephen A. Cook (J. Comput. Syst. Sci., 1974)

Corrections for "On the lengths of proofs in the propositional calculus preliminary version". - Stephen A. Cook; Robert A. Reckhow (SIGACT News, 1974)

An Assertion Language for Data Structures. - Stephen A. Cook; Derek C. Oppen (POPL, 1975)

Feasibly Constructive Proofs and the Propositional Calculus (Preliminary Version) - Stephen A. Cook (STOC, 1975)

Proving Assertions about Programs that Manipulate Data Structures - Derek C. Oppen; Stephen A. Cook (STOC, 1975)

Storage Requirements for Deterministic Polynomial Time Recognizable Languages. - Stephen A. Cook; Ravi Sethi (J. Comput. Syst. Sci., 1976)

On the Number of Additions to Compute Specific Polynomials. - Allan Borodin; Stephen A. Cook (SIAM J. Comput., 1976)

A short proof of the pigeon hole principle using extended resolution. - Stephen A. Cook (SIGACT News, 1976)

Soundness and Completeness of an Axiom System for Program Verification. - Stephen A. Cook (SIAM J. Comput., 1978)

Deterministic CFL's Are Accepted Simultaneously in Polynomial Time and Log Squared Space - Stephen A. Cook (STOC, 1979)

The Relative Efficiency of Propositional Proof Systems. - Stephen A. Cook; Robert A. Reckhow (J. Symb. Log., 1979)

Hardware Complexity and Parallel Computation (Preliminary Version) - Patrick W. Dymond; Stephen A. Cook (FOCS, 1980)

Space Lower Bounds for Maze Threadability on Restricted Machines. - Stephen A. Cook; Charles Rackoff (SIAM J. Comput., 1980)

Corrigendum: Soundness and Completeness of an Axiom System for Program Verification. - Stephen A. Cook (SIAM J. Comput., 1981)

Bounds on the Time for Parallel RAM's to Compute Simple Functions - Stephen A. Cook; Cynthia Dwork (STOC, 1982)

A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. - Allan Borodin; Stephen A. Cook (SIAM J. Comput., 1982)

The Classifikation of Problems which have Fast Parallel Algorithms. - Stephen A. Cook (FCT, 1983)

The Parallel Complexity of the Abelian Permutation Group Membership Problem - Pierre McKenzie; Stephen A. Cook (FOCS, 1983)

An Overview of Computational Complexity. - Stephen A. Cook (Commun. ACM, 1983)

Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines - Allan Borodin; Stephen A. Cook; Nicholas Pippenger (Inf. Control., 1983)

The Recognition of Deterministic CFL's in Small Time and Space - Burchard von Braunmühl; Stephen A. Cook; Kurt Mehlhorn; Rutger Verbeek (Inf. Control., 1983)

A Taxonomy of Problems with Fast Parallel Algorithms - Stephen A. Cook (Inf. Control., 1985)

A Depth-Universal Circuit. - Stephen A. Cook; H. James Hoover (SIAM J. Comput., 1985)

Log Depth Circuits for Division and Related Problems. - Paul Beame; Stephen A. Cook; H. James Hoover (SIAM J. Comput., 1986)

Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes. - Stephen A. Cook; Cynthia Dwork; Rüdiger Reischuk (SIAM J. Comput., 1986)

Problems Complete for Deterministic Logarithmic Space. - Stephen A. Cook; Pierre McKenzie (J. Algorithms, 1987)

The Parallel Complexity of Abelian Permutation Group Problems. - Pierre McKenzie; Stephen A. Cook (SIAM J. Comput., 1987)

Two applications of complementation via inductive counting. - Allan Borodin; Stephen A. Cook; Patrick W. Dymond; Walter L. Ruzzo; Martin Tompa (SCT, 1988)

Short Propositional Formulas Represent Nondeterministic Computations. - Stephen A. Cook (Inf. Process. Lett., 1988)

A Simple Parallel Algorithm for Finding a Satisfying Truth Assignment to a 2-CNF Formula. - Stephen A. Cook; Michael Luby (Inf. Process. Lett., 1988)

Characterizations of the Basic Feasible Functionals of Finite Type (Extended Abstract) - Stephen A. Cook; Bruce M. Kapron (FOCS, 1989)

Functional Interpretations of Feasibly Constructive Arithmetic (Extended Abstract) - Stephen A. Cook; Alasdair Urquhart (STOC, 1989)

Two Applications of Inductive Counting for Complementation Problems. - Allan Borodin; Stephen A. Cook; Patrick W. Dymond; Walter L. Ruzzo; Martin Tompa (SIAM J. Comput., 1989)

Erratum: Two Applications of Inductive Counting for Complementation Problems. - Allan Borodin; Stephen A. Cook; Patrick W. Dymond; Walter L. Ruzzo; Martin Tompa (SIAM J. Comput., 1989)

Complexity Theory of Parallel Time and Hardware - Patrick W. Dymond; Stephen A. Cook (Inf. Comput., 1989)

A Feasibly Constructive Lower Bound for Resolution Proofs. - Stephen A. Cook; Toniann Pitassi (Inf. Process. Lett., 1990)

A New Characterization of Mehlhorn's Polynomial Time Functionals (Extended Abstract) - Bruce M. Kapron; Stephen A. Cook (FOCS, 1991)

The optimal placement of replicas in a network using a read any - write all policy. - Irwin S. Pressman; Stephen A. Cook; Jan K. Pachl (CASCON, 1992)

A New Recursion-Theoretic Characterization of the Polytime Functions (Extended Abstract) - Stephen J. Bellantoni; Stephen A. Cook (STOC, 1992)

A New Recursion-Theoretic Characterization of the Polytime Functions. - Stephen J. Bellantoni; Stephen A. Cook (Comput. Complex., 1992)

An Optimal Parallel Algorithm for Formula Evaluation. - Samuel R. Buss; Stephen A. Cook; A. Gupta; V. Ramachandran (SIAM J. Comput., 1992)

Functional Interpretations of Feasibly Constructive Arithmetic. - Stephen A. Cook; Alasdair Urquhart (Ann. Pure Appl. Log., 1993)

Parallel Pointer Machines. - Stephen A. Cook; Patrick W. Dymond (Comput. Complex., 1993)

Finding hard instances of the satisfiability problem: A survey. - Stephen A. Cook; David G. Mitchell (Satisfiability Problem: Theory and Applications, 1996)

A New Characterization of Type-2 Feasibility. - Bruce M. Kapron; Stephen A. Cook (SIAM J. Comput., 1996)

A Tight Relationship Between Generic Oracles and Type-2 Complexity Theory. - Stephen A. Cook; Russell Impagliazzo; Tomoyuki Yamakami (Inf. Comput., 1997)

The Relative Complexity of NP Search Problems. - Paul Beame; Stephen A. Cook; Jeff Edmonds; Russell Impagliazzo; Toniann Pitassi (J. Comput. Syst. Sci., 1998)

An Exponential Lower Bound for the Size of Monotone Real Circuits. - Armin Haken; Stephen A. Cook (J. Comput. Syst. Sci., 1999)

Efficiently Approximable Real-Valued Functions - Valentine Kabanets; Charles Rackoff; Stephen A. Cook (Electron. Colloquium Comput. Complex., 2000)

A Second-Order System for Polytime Reasoning Using Graedel's Theorem. - Stephen A. Cook; Antonina Kolokolova (LICS, 2001)

A second-order system for polynomial-time reasoning based on Graedel's theorem - Stephen A. Cook; Antonina Kolokolova (Electron. Colloquium Comput. Complex., 2001)

Complexity Classes, Propositional Proof Systems, and Formal Theories. - Stephen A. Cook (LICS, 2002)

The optimal location of replicas in a network using a READ-ONE-WRITE-ALL policy. - Stephen A. Cook; Jan K. Pachl; Irwin S. Pressman (Distributed Comput., 2002)

A second-order system for polytime reasoning based on Grädel's theorem. - Stephen A. Cook; Antonina Kolokolova (Ann. Pure Appl. Log., 2003)

The importance of the P versus NP question. - Stephen A. Cook (J. ACM, 2003)

A Complete Axiomatization for Blocks World. - Stephen A. Cook; Yongmei Liu 001 (J. Log. Comput., 2003)

A Second-Order Theory for NL. - Stephen A. Cook; Antonina Kolokolova (LICS, 2004)

VTC circ: A Second-Order Theory for TCcirc. - Phuong Nguyen 001; Stephen A. Cook (LICS, 2004)

The proof complexity of linear algebra. - Michael Soltys; Stephen A. Cook (Ann. Pure Appl. Log., 2004)

Quantified propositional calculus and a second-order theory for NC1. - Stephen A. Cook; Tsuyoshi Morioka (Arch. Math. Log., 2005)

Computing over the Reals: Foundations for Scientific Computing - Mark Braverman; Stephen A. Cook (CoRR, 2005)

Comments on Beckmann's Uniform Reducts - Stephen A. Cook (CoRR, 2006)

Theories for TC0 and Other Small Complexity Classes. - Phuong Nguyen 001; Stephen A. Cook (Log. Methods Comput. Sci., 2006)

The strength of replacement in weak arithmetic. - Stephen A. Cook; Neil Thapen (ACM Trans. Comput. Log., 2006)

Consequences of the provability of NP ⊆ P/poly. - Stephen A. Cook; Jan Krajícek (J. Symb. Log., 2007)

Fractional Pebbling and Thrifty Branching Programs. - Mark Braverman; Stephen A. Cook; Pierre McKenzie; Rahul Santhanam; Dustin Wehr (FSTTCS, 2009)

Branching Programs for Tree Evaluation. - Mark Braverman; Stephen A. Cook; Pierre McKenzie; Rahul Santhanam; Dustin Wehr (MFCS, 2009)

A Formal Theory for the Complexity Class Associated with the Stable Marriage Problem. - Dai Tri Man Le; Stephen A. Cook; Yuli Ye (CSL, 2011)

Formalizing Randomized Matching Algorithms - Dai Tri Man Le; Stephen A. Cook (Log. Methods Comput. Sci., 2011)

Complexity Classes and Theories for the Comparator Circuit Value Problem - Dai Tri Man Le; Stephen A. Cook; Yuli Ye (CoRR, 2011)

Connecting Complexity Classes, Weak Formal Theories, and Propositional Proof Systems (Invited Talk). - Stephen A. Cook (CSL, 2012)

Formal Theories for Linear Algebra - Stephen A. Cook; Lila Fontes (Log. Methods Comput. Sci., 2012)

Relativized Propositional Calculus - Stephen A. Cook (CoRR, 2012)

The Complexity of Proving the Discrete Jordan Curve Theorem. - Phuong Nguyen 001; Stephen A. Cook (ACM Trans. Comput. Log., 2012)

Pebbles and Branching Programs for Tree Evaluation. - Stephen A. Cook; Pierre McKenzie; Dustin Wehr; Mark Braverman; Rahul Santhanam (ACM Trans. Comput. Theory, 2012)

Complexity Theory for Operators in Analysis. - Akitoshi Kawamura; Stephen A. Cook (ACM Trans. Comput. Theory, 2012)

Theories for Subexponential-size Bounded-depth Frege Proofs. - Kaveh Ghasemloo; Stephen A. Cook (CSL, 2013)

Average Case Lower Bounds for Monotone Switching Networks. - Yuval Filmus; Toniann Pitassi; Robert Robere; Stephen A. Cook (Electron. Colloquium Comput. Complex., 2013)

The Hardness of Being Private. - Anil Ada; Arkadev Chattopadhyay; Stephen A. Cook; Lila Fontes; Michal Koucký 001; Toniann Pitassi (ACM Trans. Comput. Theory, 2014)

The complexity of the comparator circuit value problem. - Stephen A. Cook; Yuval Filmus; Dai Tri Man Le (ACM Trans. Comput. Theory, 2014)

Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs. - Stephen A. Cook; Jeff Edmonds; Venkatesh Medabalimi; Toniann Pitassi (ICALP, 2016)

Relativizing small complexity classes and their theories. - Klaus Aehlig; Stephen A. Cook; Phuong Nguyen 001 (Comput. Complex., 2016)

Exponential Lower Bounds for Monotone Span Programs. - Stephen A. Cook; Toniann Pitassi; Robert Robere; Benjamin Rossman (Electron. Colloquium Comput. Complex., 2016)

Uniform, integral and efficient proofs for the determinant identities. - Iddo Tzameret; Stephen A. Cook (LICS, 2017)

A Survey of Classes of Primitive Recursive Functions. - Stephen A. Cook; Bruce M. Kapron (Electron. Colloquium Comput. Complex., 2017)

Uniform, Integral and Feasible Proofs for the Determinant Identities. - Iddo Tzameret; Stephen A. Cook (Electron. Colloquium Comput. Complex., 2018)

A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. - Allan Borodin; Stephen A. Cook (Logic, Automata, and Computational Complexity, 2023)

The 1982 ACM Turing Award Lecture: An Overview of Computational Complexity. - Stephen A. Cook (Logic, Automata, and Computational Complexity, 2023)

The Complexity of Theorem-Proving Procedures. - Stephen A. Cook (Logic, Automata, and Computational Complexity, 2023)

Characterizations of Pushdown Machines in Terms of Time-Bounded Computers. - Stephen A. Cook (Logic, Automata, and Computational Complexity, 2023)

Feasibly Constructive Proofs and the Propositional Calculus (Preliminary Version). - Stephen A. Cook (Logic, Automata, and Computational Complexity, 2023)

Towards a Complexity Theory of Synchronous Parallel Computation. - Stephen A. Cook (Logic, Automata, and Computational Complexity, 2023)

A Survey of Classes of Primitive Recursive Functions. - Stephen A. Cook (Logic, Automata, and Computational Complexity, 2023)

Pebbles and Branching Programs for Tree Evaluation. - Stephen A. Cook; Pierre McKenzie; Dustin Wehr; Mark Braverman; Rahul Santhanam (Logic, Automata, and Computational Complexity, 2023)

The Relative Efficiency of Propositional Proof Systems. - Stephen A. Cook; Robert A. Reckhow (Logic, Automata, and Computational Complexity, 2023)