Stephen A. Cook

According to our database, Stephen A. Cook authored at least 105 papers between 1966 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2023

The Relative Efficiency of Propositional Proof Systems.

Stephen A. Cook, Robert A. Reckhow

Proceedings of the Logic, 2023

Pebbles and Branching Programs for Tree Evaluation.

Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam

Proceedings of the Logic, 2023

A Survey of Classes of Primitive Recursive Functions.

Stephen A. Cook

Proceedings of the Logic, 2023

Towards a Complexity Theory of Synchronous Parallel Computation.

Stephen A. Cook

Proceedings of the Logic, 2023

Feasibly Constructive Proofs and the Propositional Calculus (Preliminary Version).

Stephen A. Cook

Proceedings of the Logic, 2023

Characterizations of Pushdown Machines in Terms of Time-Bounded Computers.

Stephen A. Cook

Proceedings of the Logic, 2023

The Complexity of Theorem-Proving Procedures.

Stephen A. Cook

Proceedings of the Logic, 2023

The 1982 ACM Turing Award Lecture: An Overview of Computational Complexity.

Stephen A. Cook

Proceedings of the Logic, 2023

A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation.

Allan Borodin, Stephen A. Cook

Proceedings of the Logic, 2023

2018

Uniform, Integral and Feasible Proofs for the Determinant Identities.

Iddo Tzameret, Stephen A. Cook

Electron. Colloquium Comput. Complex., 2018

2017

A Survey of Classes of Primitive Recursive Functions.

Stephen A. Cook, Bruce M. Kapron

Electron. Colloquium Comput. Complex., 2017

Uniform, integral and efficient proofs for the determinant identities.

Iddo Tzameret, Stephen A. Cook

Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

2016

Exponential Lower Bounds for Monotone Span Programs.

Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman

Electron. Colloquium Comput. Complex., 2016

Relativizing small complexity classes and their theories.

Klaus Aehlig, Stephen A. Cook, Phuong Nguyen

Comput. Complex., 2016

Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs.

Stephen A. Cook, Jeff Edmonds, Venkatesh Medabalimi, Toniann Pitassi

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2014

The complexity of the comparator circuit value problem.

Stephen A. Cook, Yuval Filmus, Dai Tri Man Le

ACM Trans. Comput. Theory, 2014

The Hardness of Being Private.

Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi

ACM Trans. Comput. Theory, 2014

2013

Average Case Lower Bounds for Monotone Switching Networks.

Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook

Electron. Colloquium Comput. Complex., 2013

Theories for Subexponential-size Bounded-depth Frege Proofs.

Kaveh Ghasemloo, Stephen A. Cook

Proceedings of the Computer Science Logic 2013 (CSL 2013), 2013

2012

Complexity Theory for Operators in Analysis.

Akitoshi Kawamura, Stephen A. Cook

ACM Trans. Comput. Theory, 2012

Pebbles and Branching Programs for Tree Evaluation.

Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam

ACM Trans. Comput. Theory, 2012

The Complexity of Proving the Discrete Jordan Curve Theorem.

Phuong Nguyen, Stephen A. Cook

ACM Trans. Comput. Log., 2012

Relativized Propositional Calculus

Stephen A. Cook

CoRR, 2012

Formal Theories for Linear Algebra

Stephen A. Cook, Lila Fontes

Log. Methods Comput. Sci., 2012

Connecting Complexity Classes, Weak Formal Theories, and Propositional Proof Systems (Invited Talk).

Stephen A. Cook

Proceedings of the Computer Science Logic (CSL'12), 2012

2011

Complexity Classes and Theories for the Comparator Circuit Value Problem

Dai Tri Man Le, Stephen A. Cook, Yuli Ye

CoRR, 2011

Formalizing Randomized Matching Algorithms

Dai Tri Man Le, Stephen A. Cook

Log. Methods Comput. Sci., 2011

A Formal Theory for the Complexity Class Associated with the Stable Marriage Problem.

Dai Tri Man Le, Stephen A. Cook, Yuli Ye

Proceedings of the Computer Science Logic, 2011

2009

Branching Programs for Tree Evaluation.

Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr

Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

Fractional Pebbling and Thrifty Branching Programs.

Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

2007

Consequences of the provability of <i>NP</i> ⊆ <i>P/poly</i>.

Stephen A. Cook, Jan Krajícek

J. Symb. Log., 2007

2006

The strength of replacement in weak arithmetic.

Stephen A. Cook, Neil Thapen

ACM Trans. Comput. Log., 2006

Theories for TC0 and Other Small Complexity Classes.

Phuong Nguyen, Stephen A. Cook

Log. Methods Comput. Sci., 2006

Comments on Beckmann's Uniform Reducts

Stephen A. Cook

CoRR, 2006

2005

Computing over the Reals: Foundations for Scientific Computing

Mark Braverman, Stephen A. Cook

CoRR, 2005

Quantified propositional calculus and a second-order theory for NC¹.

Stephen A. Cook, Tsuyoshi Morioka

Arch. Math. Log., 2005

2004

The proof complexity of linear algebra.

Michael Soltys, Stephen A. Cook

Ann. Pure Appl. Log., 2004

VTC ^circ: A Second-Order Theory for TC^circ.

Phuong Nguyen, Stephen A. Cook

Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), 2004

A Second-Order Theory for NL.

Stephen A. Cook, Antonina Kolokolova

Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), 2004

2003

A Complete Axiomatization for Blocks World.

Stephen A. Cook, Yongmei Liu

J. Log. Comput., 2003

The importance of the P versus NP question.

Stephen A. Cook

J. ACM, 2003

A second-order system for polytime reasoning based on Grädel's theorem.

Stephen A. Cook, Antonina Kolokolova

Ann. Pure Appl. Log., 2003

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

Complexity Classes, Propositional Proof Systems, and Formal Theories.

Stephen A. Cook

Proceedings of the 17th IEEE Symposium on Logic in Computer Science (LICS 2002), 2002

2001

A second-order system for polynomial-time reasoning based on Graedel's theorem

Stephen A. Cook, Antonina Kolokolova

Electron. Colloquium Comput. Complex., 2001

A Second-Order System for Polytime Reasoning Using Graedel's Theorem.

Stephen A. Cook, Antonina Kolokolova

Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, 2001

2000

Efficiently Approximable Real-Valued Functions

Valentine Kabanets, Charles Rackoff, Stephen A. Cook

Electron. Colloquium Comput. Complex., 2000

1999

An Exponential Lower Bound for the Size of Monotone Real Circuits.

Armin Haken, Stephen A. Cook

J. Comput. Syst. Sci., 1999

1998

The Relative Complexity of NP Search Problems.

Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi

J. Comput. Syst. Sci., 1998

1997

A Tight Relationship Between Generic Oracles and Type-2 Complexity Theory.

Stephen A. Cook, Russell Impagliazzo, Tomoyuki Yamakami

Inf. Comput., 1997

1996

A New Characterization of Type-2 Feasibility.

Bruce M. Kapron, Stephen A. Cook

SIAM J. Comput., 1996

Finding hard instances of the satisfiability problem: A survey.

Stephen A. Cook, David G. Mitchell

Proceedings of the Satisfiability Problem: Theory and Applications, 1996

1993

Parallel Pointer Machines.

Stephen A. Cook, Patrick W. Dymond

Comput. Complex., 1993

Functional Interpretations of Feasibly Constructive Arithmetic.

Stephen A. Cook, Alasdair Urquhart

Ann. Pure Appl. Log., 1993

1992

An Optimal Parallel Algorithm for Formula Evaluation.

Samuel R. Buss, Stephen A. Cook, A. Gupta, V. Ramachandran

SIAM J. Comput., 1992

A New Recursion-Theoretic Characterization of the Polytime Functions.

Stephen J. Bellantoni, Stephen A. Cook

Comput. Complex., 1992

A New Recursion-Theoretic Characterization of the Polytime Functions (Extended Abstract)

Stephen J. Bellantoni, Stephen A. Cook

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

The optimal placement of replicas in a network using a read any - write all policy.

Irwin S. Pressman, Stephen A. Cook, Jan K. Pachl

Proceedings of the 1992 Conference of the Centre for Advanced Studies on Collaborative Research, 1992

1991

A New Characterization of Mehlhorn's Polynomial Time Functionals (Extended Abstract)

Bruce M. Kapron, Stephen A. Cook

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990

A Feasibly Constructive Lower Bound for Resolution Proofs.

Stephen A. Cook, Toniann Pitassi

Inf. Process. Lett., 1990

1989

Complexity Theory of Parallel Time and Hardware

Patrick W. Dymond, Stephen A. Cook

Inf. Comput., March, 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

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

Functional Interpretations of Feasibly Constructive Arithmetic (Extended Abstract)

Stephen A. Cook, Alasdair Urquhart

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Characterizations of the Basic Feasible Functionals of Finite Type (Extended Abstract)

Stephen A. Cook, Bruce M. Kapron

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

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

Short Propositional Formulas Represent Nondeterministic Computations.

Stephen A. Cook

Inf. Process. Lett., 1988

Two applications of complementation via inductive counting.

Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, Martin Tompa

Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987

The Parallel Complexity of Abelian Permutation Group Problems.

Pierre McKenzie, Stephen A. Cook

SIAM J. Comput., 1987

Problems Complete for Deterministic Logarithmic Space.

Stephen A. Cook, Pierre McKenzie

J. Algorithms, 1987

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

Log Depth Circuits for Division and Related Problems.

Paul Beame, Stephen A. Cook, H. James Hoover

SIAM J. Comput., 1986

1985

A Depth-Universal Circuit.

Stephen A. Cook, H. James Hoover

SIAM J. Comput., 1985

A Taxonomy of Problems with Fast Parallel Algorithms

Stephen A. Cook

Inf. Control., 1985

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

Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines

Allan Borodin, Stephen A. Cook, Nicholas Pippenger

Inf. Control., 1983

An Overview of Computational Complexity.

Stephen A. Cook

Commun. ACM, 1983

The Parallel Complexity of the Abelian Permutation Group Membership Problem

Pierre McKenzie, Stephen A. Cook

Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

The Classifikation of Problems which have Fast Parallel Algorithms.

Stephen A. Cook

Proceedings of the Fundamentals of Computation Theory, 1983

1982

A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation.

Allan Borodin, Stephen A. Cook

SIAM J. Comput., 1982

Bounds on the Time for Parallel RAM's to Compute Simple Functions

Stephen A. Cook, Cynthia Dwork

Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

1981

Corrigendum: Soundness and Completeness of an Axiom System for Program Verification.

Stephen A. Cook

SIAM J. Comput., 1981

1980

Space Lower Bounds for Maze Threadability on Restricted Machines.

Stephen A. Cook, Charles Rackoff

SIAM J. Comput., 1980

Hardware Complexity and Parallel Computation (Preliminary Version)

Patrick W. Dymond, Stephen A. Cook

Proceedings of the 21st Annual Symposium on Foundations of Computer Science, 1980

1979

The Relative Efficiency of Propositional Proof Systems.

Stephen A. Cook, Robert A. Reckhow

J. Symb. Log., 1979

Deterministic CFL's Are Accepted Simultaneously in Polynomial Time and Log Squared Space

Stephen A. Cook

Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979

1978

Soundness and Completeness of an Axiom System for Program Verification.

Stephen A. Cook

SIAM J. Comput., 1978

1976

A short proof of the pigeon hole principle using extended resolution.

Stephen A. Cook

SIGACT News, 1976

On the Number of Additions to Compute Specific Polynomials.

Allan Borodin, Stephen A. Cook

SIAM J. Comput., 1976

Storage Requirements for Deterministic Polynomial Time Recognizable Languages.

Stephen A. Cook, Ravi Sethi

J. Comput. Syst. Sci., 1976

1975

Proving Assertions about Programs that Manipulate Data Structures

Derek C. Oppen, Stephen A. Cook

Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

Feasibly Constructive Proofs and the Propositional Calculus (Preliminary Version)

Stephen A. Cook

Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

An Assertion Language for Data Structures.

Stephen A. Cook, Derek C. Oppen

Proceedings of the Conference Record of the Second ACM Symposium on Principles of Programming Languages, 1975

1974

Corrections for "On the lengths of proofs in the propositional calculus preliminary version".

Stephen A. Cook, Robert A. Reckhow

SIGACT News, 1974

An Observation on Time-Storage Trade Off.

Stephen A. Cook

J. Comput. Syst. Sci., 1974

On the Lengths of Proofs in the Propositional Calculus (Preliminary Version)

Stephen A. Cook, Robert A. Reckhow

Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

On the Number of Additions to Compute Specific Polynomials (Preliminary Version)

Allan Borodin, Stephen A. Cook

Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

1973

Time Bounded Random Access Machines.

Stephen A. Cook, Robert A. Reckhow

J. Comput. Syst. Sci., 1973

A Hierarchy for Nondeterministic Time Complexity.

Stephen A. Cook

J. Comput. Syst. Sci., 1973

1971

Characterizations of Pushdown Machines in Terms of Time-Bounded Computers.

Stephen A. Cook

J. ACM, 1971

The Complexity of Theorem-Proving Procedures

Stephen A. Cook

Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971

Linear Time Simulation of Deterministic Two-Way Pushdown Automata.

Stephen A. Cook

Proceedings of the Information Processing, Proceedings of IFIP Congress 1971, Volume 1, 1971

1970

Path Systems and Language Recognition

Stephen A. Cook

Proceedings of the 2nd Annual ACM Symposium on Theory of Computing, 1970

1969

Variations on Pushdown Machines (Detailed Abstract)

Stephen A. Cook

Proceedings of the 1st Annual ACM Symposium on Theory of Computing, 1969

1966

The Solvability of the Derivability Problem for One-Normal Systems.

Stephen A. Cook

J. ACM, 1966