| 2007 |
|---|
| 71 | EE | Phuong Nguyen,
Stephen A. Cook:
The Complexity of Proving the Discrete Jordan Curve Theorem.
LICS 2007: 245-256 |
| 2006 |
|---|
| 70 | EE | Stephen A. Cook,
Neil Thapen:
The strength of replacement in weak arithmetic.
ACM Trans. Comput. Log. 7(4): 749-764 (2006) |
| 69 | EE | Phuong Nguyen,
Stephen A. Cook:
Theories for TC0 and Other Small Complexity Classes.
Logical Methods in Computer Science 2(1): (2006) |
| 2004 |
|---|
| 68 | EE | Stephen A. Cook,
Neil Thapen:
The Strength of Replacement in Weak Arithmetic.
LICS 2004: 256-264 |
| 67 | EE | Phuong Nguyen,
Stephen A. Cook:
VTC circ: A Second-Order Theory for TCcirc.
LICS 2004: 378-387 |
| 66 | EE | Stephen A. Cook,
Antonina Kolokolova:
A Second-Order Theory for NL.
LICS 2004: 398-407 |
| 65 | EE | Michael Soltys,
Stephen A. Cook:
The proof complexity of linear algebra.
Ann. Pure Appl. Logic 130(1-3): 277-323 (2004) |
| 64 | EE | Stephen A. Cook,
Neil Thapen:
The strength of replacement in weak arithmetic
CoRR cs.LO/0409015: (2004) |
| 2003 |
|---|
| 63 | EE | Stephen A. Cook,
Antonina Kolokolova:
A second-order system for polytime reasoning based on Grädel's theorem.
Ann. Pure Appl. Logic 124(1-3): 193-231 (2003) |
| 62 | EE | Stephen A. Cook:
The importance of the P versus NP question.
J. ACM 50(1): 27-29 (2003) |
| 61 | EE | Stephen A. Cook,
Yongmei Liu:
A Complete Axiomatization for Blocks World.
J. Log. Comput. 13(4): 581-594 (2003) |
| 2002 |
|---|
| 60 | EE | Stephen A. Cook,
Yongmei Liu:
A Complete Axiomatization for Blocks World.
AMAI 2002 |
| 59 | EE | Stephen A. Cook:
Complexity Classes, Propositional Proof Systems, and Formal Theories.
LICS 2002: 311 |
| 58 | EE | Michael Soltys,
Stephen A. Cook:
The Proof Complexity of Linear Algebra.
LICS 2002: 335-344 |
| 57 | EE | Stephen A. Cook,
Jan K. Pachl,
Irwin S. Pressman:
The optimal location of replicas in a network using a READ-ONE-WRITE-ALL policy.
Distributed Computing 15(1): 57-66 (2002) |
| 2001 |
|---|
| 56 | | Stephen A. Cook,
Antonina Kolokolova:
A Second-Order System for Polytime Reasoning Using Graedel's Theorem.
LICS 2001: 177-186 |
| 55 | EE | Stephen A. Cook,
Antonina Kolokolova:
A second-order system for polynomial-time reasoning based on Graedel's theorem
Electronic Colloquium on Computational Complexity (ECCC) 8(24): (2001) |
| 1999 |
|---|
| 54 | | Armin Haken,
Stephen A. Cook:
An Exponential Lower Bound for the Size of Monotone Real Circuits.
J. Comput. Syst. Sci. 58(2): 326-335 (1999) |
| 1998 |
|---|
| 53 | | Paul Beame,
Stephen A. Cook,
Jeff Edmonds,
Russell Impagliazzo,
Toniann Pitassi:
The Relative Complexity of NP Search Problems.
J. Comput. Syst. Sci. 57(1): 3-19 (1998) |
| 1997 |
|---|
| 52 | | Stephen A. Cook,
Russell Impagliazzo,
Tomoyuki Yamakami:
A Tight Relationship Between Generic Oracles and Type-2 Complexity Theory.
Inf. Comput. 137(2): 159-170 (1997) |
| 1995 |
|---|
| 51 | EE | Paul Beame,
Stephen A. Cook,
Jeff Edmonds,
Russell Impagliazzo,
Toniann Pitassi:
The relative complexity of NP search problems.
STOC 1995: 303-314 |
| 1993 |
|---|
| 50 | | Stephen A. Cook,
Alasdair Urquhart:
Functional Interpretations of Feasibly Constructive Arithmetic.
Ann. Pure Appl. Logic 63(2): 103-200 (1993) |
| 49 | | Stephen A. Cook,
Patrick W. Dymond:
Parallel Pointer Machines.
Computational Complexity 3: 19-30 (1993) |
| 1992 |
|---|
| 48 | EE | Irwin S. Pressman,
Stephen A. Cook,
Jan K. Pachl:
The optimal placement of replicas in a network using a read any - write all policy.
CASCON 1992: 189-201 |
| 47 | | Stephen Bellantoni,
Stephen A. Cook:
A New Recursion-Theoretic Characterization of the Polytime Functions (Extended Abstract)
STOC 1992: 283-293 |
| 46 | | Stephen Bellantoni,
Stephen A. Cook:
A New Recursion-Theoretic Characterization of the Polytime Functions.
Computational Complexity 2: 97-110 (1992) |
| 1991 |
|---|
| 45 | | Bruce M. Kapron,
Stephen A. Cook:
A New Characterization of Mehlhorn's Polynomial Time Functionals (Extended Abstract)
FOCS 1991: 342-347 |
| 1990 |
|---|
| 44 | | Stephen A. Cook,
Toniann Pitassi:
A Feasibly Constructive Lower Bound for Resolution Proofs.
Inf. Process. Lett. 34(2): 81-85 (1990) |
| 1989 |
|---|
| 43 | | Stephen A. Cook,
Bruce M. Kapron:
Characterizations of the Basic Feasible Functionals of Finite Type (Extended Abstract)
FOCS 1989: 154-159 |
| 42 | | Stephen A. Cook,
Alasdair Urquhart:
Functional Interpretations of Feasibly Constructive Arithmetic (Extended Abstract)
STOC 1989: 107-112 |
| 41 | | Patrick W. Dymond,
Stephen A. Cook:
Complexity Theory of Parallel Time and Hardware
Inf. Comput. 80(3): 205-226 (1989) |
| 40 | | Allan Borodin,
Stephen A. Cook,
Patrick W. Dymond,
Walter L. Ruzzo,
Martin Tompa:
Two Applications of Inductive Counting for Complementation Problems.
SIAM J. Comput. 18(3): 559-578 (1989) |
| 39 | | Allan Borodin,
Stephen A. Cook,
Patrick W. Dymond,
Walter L. Ruzzo,
Martin Tompa:
Erratum: Two Applications of Inductive Counting for Complementation Problems.
SIAM J. Comput. 18(6): 1283 (1989) |
| 1988 |
|---|
| 38 | | Stephen A. Cook:
Short Propositional Formulas Represent Nondeterministic Computations.
Inf. Process. Lett. 26(5): 269-270 (1988) |
| 37 | | Stephen A. Cook,
Michael Luby:
A Simple Parallel Algorithm for Finding a Satisfying Truth Assignment to a 2-CNF Formula.
Inf. Process. Lett. 27(3): 141-145 (1988) |
| 1987 |
|---|
| 36 | | Stephen A. Cook,
Pierre McKenzie:
Problems Complete for Deterministic Logarithmic Space.
J. Algorithms 8(3): 385-394 (1987) |
| 35 | | Pierre McKenzie,
Stephen A. Cook:
The Parallel Complexity of Abelian Permutation Group Problems.
SIAM J. Comput. 16(5): 880-909 (1987) |
| 1986 |
|---|
| 34 | | Paul Beame,
Stephen A. Cook,
H. James Hoover:
Log Depth Circuits for Division and Related Problems.
SIAM J. Comput. 15(4): 994-1003 (1986) |
| 1985 |
|---|
| 33 | | Stephen A. Cook:
A Taxonomy of Problems with Fast Parallel Algorithms
Information and Control 64(1-3): 2-21 (1985) |
| 32 | | Stephen A. Cook,
H. James Hoover:
A Depth-Universal Circuit.
SIAM J. Comput. 14(4): 833-839 (1985) |
| 1984 |
|---|
| 31 | | Paul Beame,
Stephen A. Cook,
H. James Hoover:
Log Depth Circuits for Division and Related Problems
FOCS 1984: 1-6 |
| 1983 |
|---|
| 30 | | Stephen A. Cook:
The Classifikation of Problems which have Fast Parallel Algorithms.
FCT 1983: 78-93 |
| 29 | | Pierre McKenzie,
Stephen A. Cook:
The Parallel Complexity of the Abelian Permutation Group Membership Problem
FOCS 1983: 154-161 |
| 28 | | Stephen A. Cook:
An Overview of Computational Complexity.
Commun. ACM 26(6): 400-408 (1983) |
| 27 | | Allan Borodin,
Stephen A. Cook,
Nicholas Pippenger:
Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines
Information and Control 58(1-3): 113-136 (1983) |
| 1982 |
|---|
| 26 | | Allan Borodin,
Stephen A. Cook:
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation.
SIAM J. Comput. 11(2): 287-297 (1982) |
| 1981 |
|---|
| 25 | | Stephen A. Cook:
Corrigendum: Soundness and Completeness of an Axiom System for Program Verification.
SIAM J. Comput. 10(3): 612 (1981) |
| 1980 |
|---|
| 24 | | Patrick W. Dymond,
Stephen A. Cook:
Hardware Complexity and Parallel Computation (Preliminary Version)
FOCS 1980: 360-372 |
| 23 | | Allan Borodin,
Stephen A. Cook:
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
STOC 1980: 294-301 |
| 22 | | Stephen A. Cook,
Charles Rackoff:
Space Lower Bounds for Maze Threadability on Restricted Machines.
SIAM J. Comput. 9(3): 636-652 (1980) |
| 1979 |
|---|
| 21 | | Stephen A. Cook:
Deterministic CFL's Are Accepted Simultaneously in Polynomial Time and Log Squared Space
STOC 1979: 338-345 |
| 20 | | Stephen A. Cook,
Robert A. Reckhow:
The Relative Efficiency of Propositional Proof Systems.
J. Symb. Log. 44(1): 36-50 (1979) |
| 1978 |
|---|
| 19 | | Stephen A. Cook:
Soundness and Completeness of an Axiom System for Program Verification.
SIAM J. Comput. 7(1): 70-90 (1978) |
| 1976 |
|---|
| 18 | | Stephen A. Cook,
Ravi Sethi:
Storage Requirements for Deterministic Polynomial Time Recognizable Languages.
J. Comput. Syst. Sci. 13(1): 25-37 (1976) |
| 17 | | Allan Borodin,
Stephen A. Cook:
On the Number of Additions to Compute Specific Polynomials.
SIAM J. Comput. 5(1): 146-157 (1976) |
| 1975 |
|---|
| 16 | | Stephen A. Cook,
Derek C. Oppen:
An Assertion Language for Data Structures.
POPL 1975: 160-166 |
| 15 | | Derek C. Oppen,
Stephen A. Cook:
Proving Assertions about Programs that Manipulate Data Structures
STOC 1975: 107-116 |
| 14 | | Stephen A. Cook:
Feasibly Constructive Proofs and the Propositional Calculus (Preliminary Version)
STOC 1975: 83-97 |
| 1974 |
|---|
| 13 | | Stephen A. Cook,
Robert A. Reckhow:
On the Lengths of Proofs in the Propositional Calculus (Preliminary Version)
STOC 1974: 135-148 |
| 12 | | Allan Borodin,
Stephen A. Cook:
On the Number of Additions to Compute Specific Polynomials (Preliminary Version)
STOC 1974: 342-347 |
| 11 | | Stephen A. Cook:
An Observation on Time-Storage Trade Off.
J. Comput. Syst. Sci. 9(3): 308-316 (1974) |
| 1973 |
|---|
| 10 | | Stephen A. Cook:
An Observation on Time-Storage Trade Off
STOC 1973: 29-33 |
| 9 | | Stephen A. Cook:
A Hierarchy for Nondeterministic Time Complexity.
J. Comput. Syst. Sci. 7(4): 343-353 (1973) |
| 8 | | Stephen A. Cook,
Robert A. Reckhow:
Time Bounded Random Access Machines.
J. Comput. Syst. Sci. 7(4): 354-375 (1973) |
| 1972 |
|---|
| 7 | | Stephen A. Cook:
A Hierarchy for Nondeterministic Time Complexity
STOC 1972: 187-192 |
| 6 | | Stephen A. Cook,
Robert A. Reckhow:
Time-Bounded Random Access Machines
STOC 1972: 73-80 |
| 1971 |
|---|
| 5 | | Stephen A. Cook:
The Complexity of Theorem-Proving Procedures
STOC 1971: 151-158 |
| 4 | EE | Stephen A. Cook:
Characterizations of Pushdown Machines in Terms of Time-Bounded Computers.
J. ACM 18(1): 4-18 (1971) |
| 1970 |
|---|
| 3 | | Stephen A. Cook:
Path Systems and Language Recognition
STOC 1970: 70-72 |
| 1969 |
|---|
| 2 | | Stephen A. Cook:
Variations on Pushdown Machines (Detailed Abstract)
STOC 1969: 229-231 |
| 1966 |
|---|
| 1 | EE | Stephen A. Cook:
The Solvability of the Derivability Problem for One-Normal Systems.
J. ACM 13(2): 223-225 (1966) |
