Stephen A. Cook

Publication Activity (10 Years)

Years Active: 1966-2021
Publications (10 Years): 9

Top Venues

CoRR

ACM Trans. Comput. Theory

Electron. Colloquium Comput. Complex.

FOCS

Publications

Iddo Tzameret, Stephen A. Cook
Uniform, Integral, and Feasible Proofs for the Determinant Identities. J. ACM 68 (2) (2021)
Iddo Tzameret, Stephen A. Cook
Uniform, Integral and Feasible Proofs for the Determinant Identities. Electron. Colloquium Comput. Complex. 25 (2018)
Iddo Tzameret, Stephen A. Cook
Uniform, Integral and Feasible Proofs for the Determinant Identities. CoRR (2018)
Stephen A. Cook, Bruce M. Kapron
A Survey of Classes of Primitive Recursive Functions. Electron. Colloquium Comput. Complex. 24 (2017)
Iddo Tzameret, Stephen A. Cook
Uniform, integral and efficient proofs for the determinant identities. LICS (2017)
Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman
Exponential Lower Bounds for Monotone Span Programs. Electron. Colloquium Comput. Complex. 23 (2016)
Stephen A. Cook, Jeff Edmonds, Venkatesh Medabalimi, Toniann Pitassi
Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs. ICALP (2016)
Robert Robere, Toniann Pitassi, Benjamin Rossman, Stephen A. Cook
Exponential Lower Bounds for Monotone Span Programs. FOCS (2016)
Klaus Aehlig, Stephen A. Cook, Phuong Nguyen
Relativizing small complexity classes and their theories. Comput. Complex. 25 (1) (2016)
Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi
The Hardness of Being Private. ACM Trans. Comput. Theory 6 (1) (2014)
Stephen A. Cook, Yuval Filmus, Dai Tri Man Le
The complexity of the comparator circuit value problem. ACM Trans. Comput. Theory 6 (4) (2014)
Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook
Average Case Lower Bounds for Monotone Switching Networks. FOCS (2013)
Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook
Average Case Lower Bounds for Monotone Switching Networks. Electron. Colloquium Comput. Complex. 20 (2013)
Akitoshi Kawamura, Stephen A. Cook
Complexity Theory for Operators in Analysis CoRR (2013)
Kaveh Ghasemloo, Stephen A. Cook
Theories for Subexponential-size Bounded-depth Frege Proofs. CSL (2013)
Akitoshi Kawamura, Stephen A. Cook
Complexity Theory for Operators in Analysis. ACM Trans. Comput. Theory 4 (2) (2012)
Stephen A. Cook, Lila Fontes
Formal Theories for Linear Algebra Log. Methods Comput. Sci. 8 (1) (2012)
Klaus Aehlig, Stephen A. Cook, Phuong Nguyen
Relativizing Small Complexity Classes and their Theories CoRR (2012)
Stephen A. Cook
Relativized Propositional Calculus CoRR (2012)
Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi
The Hardness of Being Private. Computational Complexity Conference (2012)
Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam
Pebbles and Branching Programs for Tree Evaluation. ACM Trans. Comput. Theory 3 (2) (2012)
Phuong Nguyen, Stephen A. Cook
The Complexity of Proving the Discrete Jordan Curve Theorem. ACM Trans. Comput. Log. 13 (1) (2012)
Stephen A. Cook
Connecting Complexity Classes, Weak Formal Theories, and Propositional Proof Systems (Invited Talk). CSL (2012)
Stephen A. Cook, Yuval Filmus, Dai Tri Man Le
The Complexity of the Comparator Circuit Value Problem CoRR (2012)
Dai Tri Man Le, Stephen A. Cook
Formalizing Randomized Matching Algorithms. LICS (2011)
Dai Tri Man Le, Stephen A. Cook
Formalizing Randomized Matching Algorithms Log. Methods Comput. Sci. 8 (3) (2011)
Dai Tri Man Le, Stephen A. Cook, Yuli Ye
Complexity Classes and Theories for the Comparator Circuit Value Problem CoRR (2011)
Dai Tri Man Le, Stephen A. Cook, Yuli Ye
A Formal Theory for the Complexity Class Associated with the Stable Marriage Problem. CSL (2011)
Akitoshi Kawamura, Stephen A. Cook
Complexity theory for operators in analysis. STOC (2010)
Phuong Nguyen, Stephen A. Cook
The Complexity of Proving the Discrete Jordan Curve Theorem CoRR (2010)
Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam
Pebbles and Branching Programs for Tree Evaluation CoRR (2010)
Stephen A. Cook, Lila Fontes
Formal Theories for Linear Algebra. CSL (2010)
Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr
Branching Programs for Tree Evaluation. MFCS (2009)
Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr
Fractional Pebbling and Thrifty Branching Programs. FSTTCS (2009)
Phuong Nguyen, Stephen A. Cook
The Complexity of Proving the Discrete Jordan Curve Theorem. LICS (2007)
Klaus Aehlig, Stephen A. Cook, Phuong Nguyen
Relativizing Small Complexity Classes and Their Theories. CSL (2007)
Stephen A. Cook, Jan Krajícek
. J. Symb. Log. 72 (4) (2007)
Stephen A. Cook, Neil Thapen
The strength of replacement in weak arithmetic. ACM Trans. Comput. Log. 7 (4) (2006)
Phuong Nguyen, Stephen A. Cook
Theories for TC0 and Other Small Complexity Classes. Log. Methods Comput. Sci. 2 (1) (2006)
Stephen A. Cook
Comments on Beckmann's Uniform Reducts CoRR (2006)
Mark Braverman, Stephen A. Cook
Computing over the Reals: Foundations for Scientific Computing CoRR (2005)
Stephen A. Cook, Tsuyoshi Morioka
. Arch. Math. Log. 44 (6) (2005)
Phuong Nguyen, Stephen A. Cook
Theories for TC0 and Other Small Complexity Classes CoRR (2005)
Michael Soltys, Stephen A. Cook
The proof complexity of linear algebra. Ann. Pure Appl. Log. 130 (1-3) (2004)
Stephen A. Cook, Neil Thapen
The strength of replacement in weak arithmetic CoRR (2004)
Stephen A. Cook, Neil Thapen
The Strength of Replacement in Weak Arithmetic. LICS (2004)
Stephen A. Cook, Antonina Kolokolova
A Second-Order Theory for NL. LICS (2004)
Phuong Nguyen, Stephen A. Cook
. LICS (2004)
Stephen A. Cook
The importance of the P versus NP question. J. ACM 50 (1) (2003)
Stephen A. Cook, Yongmei Liu
A Complete Axiomatization for Blocks World. J. Log. Comput. 13 (4) (2003)
Stephen A. Cook, Antonina Kolokolova
A second-order system for polytime reasoning based on Grädel's theorem. Ann. Pure Appl. Log. 124 (1-3) (2003)
Stephen A. Cook
Complexity Classes, Propositional Proof Systems, and Formal Theories. LICS (2002)
Michael Soltys, Stephen A. Cook
The Proof Complexity of Linear Algebra. LICS (2002)
Stephen A. Cook, Yongmei Liu
A Complete Axiomatization for Blocks World. AI&M (2002)
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 Comput. 15 (1) (2002)
Stephen A. Cook, Antonina Kolokolova
A second-order system for polynomial-time reasoning based on Graedel's theorem Electron. Colloquium Comput. Complex. 8 (24) (2001)
Stephen A. Cook, Antonina Kolokolova
A Second-Order System for Polytime Reasoning Using Graedel's Theorem. LICS (2001)
Valentine Kabanets, Charles Rackoff, Stephen A. Cook
Efficiently Approximable Real-Valued Functions Electron. Colloquium Comput. Complex. 7 (34) (2000)
Armin Haken, Stephen A. Cook
An Exponential Lower Bound for the Size of Monotone Real Circuits. J. Comput. Syst. Sci. 58 (2) (1999)
Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi
The Relative Complexity of NP Search Problems. J. Comput. Syst. Sci. 57 (1) (1998)
Stephen A. Cook, Russell Impagliazzo, Tomoyuki Yamakami
A Tight Relationship Between Generic Oracles and Type-2 Complexity Theory. Inf. Comput. 137 (2) (1997)
Stephen A. Cook, David G. Mitchell
Finding hard instances of the satisfiability problem: A survey. Satisfiability Problem: Theory and Applications (1996)
Bruce M. Kapron, Stephen A. Cook
A New Characterization of Type-2 Feasibility. SIAM J. Comput. 25 (1) (1996)
Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi
The relative complexity of NP search problems. STOC (1995)
Stephen A. Cook, Alasdair Urquhart
Functional Interpretations of Feasibly Constructive Arithmetic. Ann. Pure Appl. Log. 63 (2) (1993)
Stephen A. Cook, Patrick W. Dymond
Parallel Pointer Machines. Comput. Complex. 3 (1993)
Stephen J. Bellantoni, Stephen A. Cook
A New Recursion-Theoretic Characterization of the Polytime Functions. Comput. Complex. 2 (1992)
Samuel R. Buss, Stephen A. Cook, A. Gupta, V. Ramachandran
An Optimal Parallel Algorithm for Formula Evaluation. SIAM J. Comput. 21 (4) (1992)
Stephen J. Bellantoni, Stephen A. Cook
A New Recursion-Theoretic Characterization of the Polytime Functions (Extended Abstract) STOC (1992)
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)
Bruce M. Kapron, Stephen A. Cook
A New Characterization of Mehlhorn's Polynomial Time Functionals (Extended Abstract) FOCS (1991)
Stephen A. Cook, Toniann Pitassi
A Feasibly Constructive Lower Bound for Resolution Proofs. Inf. Process. Lett. 34 (2) (1990)
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) (1989)
Patrick W. Dymond, Stephen A. Cook
Complexity Theory of Parallel Time and Hardware Inf. Comput. 80 (3) (1989)
Stephen A. Cook, Alasdair Urquhart
Functional Interpretations of Feasibly Constructive Arithmetic (Extended Abstract) STOC (1989)
Stephen A. Cook, Bruce M. Kapron
Characterizations of the Basic Feasible Functionals of Finite Type (Extended Abstract) FOCS (1989)
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) (1989)
Stephen A. Cook
Short Propositional Formulas Represent Nondeterministic Computations. Inf. Process. Lett. 26 (5) (1988)
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) (1988)
Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, Martin Tompa
Two applications of complementation via inductive counting. Computational Complexity Conference (1988)
Stephen A. Cook, Pierre McKenzie
Problems Complete for Deterministic Logarithmic Space. J. Algorithms 8 (3) (1987)
Pierre McKenzie, Stephen A. Cook
The Parallel Complexity of Abelian Permutation Group Problems. SIAM J. Comput. 16 (5) (1987)
Stephen A. Cook, Cynthia Dwork, Rüdiger Reischuk
Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes. SIAM J. Comput. 15 (1) (1986)
Paul Beame, Stephen A. Cook, H. James Hoover
Log Depth Circuits for Division and Related Problems. SIAM J. Comput. 15 (4) (1986)
Stephen A. Cook
A Taxonomy of Problems with Fast Parallel Algorithms Inf. Control. 64 (1-3) (1985)
Stephen A. Cook, H. James Hoover
A Depth-Universal Circuit. SIAM J. Comput. 14 (4) (1985)
Paul Beame, Stephen A. Cook, H. James Hoover
Log Depth Circuits for Division and Related Problems FOCS (1984)
Allan Borodin, Stephen A. Cook, Nicholas Pippenger
Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines Inf. Control. 58 (1-3) (1983)
Burchard von Braunmühl, Stephen A. Cook, Kurt Mehlhorn, Rutger Verbeek
The Recognition of Deterministic CFL's in Small Time and Space Inf. Control. 56 (1/2) (1983)
Stephen A. Cook
An Overview of Computational Complexity. Commun. ACM 26 (6) (1983)
Pierre McKenzie, Stephen A. Cook
The Parallel Complexity of the Abelian Permutation Group Membership Problem FOCS (1983)
Stephen A. Cook
The Classifikation of Problems which have Fast Parallel Algorithms. FCT (1983)
Allan Borodin, Stephen A. Cook
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. SIAM J. Comput. 11 (2) (1982)
Stephen A. Cook, Cynthia Dwork
Bounds on the Time for Parallel RAM's to Compute Simple Functions STOC (1982)
Stephen A. Cook
Corrigendum: Soundness and Completeness of an Axiom System for Program Verification. SIAM J. Comput. 10 (3) (1981)
Allan Borodin, Stephen A. Cook
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation STOC (1980)
Stephen A. Cook, Charles Rackoff
Space Lower Bounds for Maze Threadability on Restricted Machines. SIAM J. Comput. 9 (3) (1980)
Patrick W. Dymond, Stephen A. Cook
Hardware Complexity and Parallel Computation (Preliminary Version) FOCS (1980)
Stephen A. Cook, Robert A. Reckhow
The Relative Efficiency of Propositional Proof Systems. J. Symb. Log. 44 (1) (1979)
Stephen A. Cook
Deterministic CFL's Are Accepted Simultaneously in Polynomial Time and Log Squared Space STOC (1979)

Stephen A. Cook.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Stephen A. Cook