Stephen A. Cook

Affiliations:
  • University of Toronto, Canada


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

Collaborative distances:

Awards

Turing Prize recipient

Turing Prize 1982, "For his advancement of our understanding of the complexity of computation in a significant and profound way".

ACM Fellow

ACM Fellow 2008, "For fundamental contributions to the theory of computational complexity.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
The Relative Efficiency of Propositional Proof Systems.
Proceedings of the Logic, 2023

Pebbles and Branching Programs for Tree Evaluation.
Proceedings of the Logic, 2023

A Survey of Classes of Primitive Recursive Functions.
Proceedings of the Logic, 2023

Towards a Complexity Theory of Synchronous Parallel Computation.
Proceedings of the Logic, 2023

Feasibly Constructive Proofs and the Propositional Calculus (Preliminary Version).
Proceedings of the Logic, 2023

Characterizations of Pushdown Machines in Terms of Time-Bounded Computers.
Proceedings of the Logic, 2023

The Complexity of Theorem-Proving Procedures.
Proceedings of the Logic, 2023

The 1982 ACM Turing Award Lecture: An Overview of Computational Complexity.
Proceedings of the Logic, 2023

A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation.
Proceedings of the Logic, 2023

2018
Uniform, Integral and Feasible Proofs for the Determinant Identities.
Electron. Colloquium Comput. Complex., 2018

2017
A Survey of Classes of Primitive Recursive Functions.
Electron. Colloquium Comput. Complex., 2017

Uniform, integral and efficient proofs for the determinant identities.
Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

2016
Exponential Lower Bounds for Monotone Span Programs.
Electron. Colloquium Comput. Complex., 2016

Relativizing small complexity classes and their theories.
Comput. Complex., 2016

Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2014
The complexity of the comparator circuit value problem.
ACM Trans. Comput. Theory, 2014

The Hardness of Being Private.
ACM Trans. Comput. Theory, 2014

2013
Average Case Lower Bounds for Monotone Switching Networks.
Electron. Colloquium Comput. Complex., 2013

Theories for Subexponential-size Bounded-depth Frege Proofs.
Proceedings of the Computer Science Logic 2013 (CSL 2013), 2013

2012
Complexity Theory for Operators in Analysis.
ACM Trans. Comput. Theory, 2012

Pebbles and Branching Programs for Tree Evaluation.
ACM Trans. Comput. Theory, 2012

The Complexity of Proving the Discrete Jordan Curve Theorem.
ACM Trans. Comput. Log., 2012

Relativized Propositional Calculus
CoRR, 2012

Formal Theories for Linear Algebra
Log. Methods Comput. Sci., 2012

Connecting Complexity Classes, Weak Formal Theories, and Propositional Proof Systems (Invited Talk).
Proceedings of the Computer Science Logic (CSL'12), 2012

2011
Complexity Classes and Theories for the Comparator Circuit Value Problem
CoRR, 2011

Formalizing Randomized Matching Algorithms
Log. Methods Comput. Sci., 2011

A Formal Theory for the Complexity Class Associated with the Stable Marriage Problem.
Proceedings of the Computer Science Logic, 2011

2009
Branching Programs for Tree Evaluation.
Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

Fractional Pebbling and Thrifty Branching Programs.
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>.
J. Symb. Log., 2007

2006
The strength of replacement in weak arithmetic.
ACM Trans. Comput. Log., 2006

Theories for TC0 and Other Small Complexity Classes.
Log. Methods Comput. Sci., 2006

Comments on Beckmann's Uniform Reducts
CoRR, 2006

2005
Computing over the Reals: Foundations for Scientific Computing
CoRR, 2005

Quantified propositional calculus and a second-order theory for NC<sup>1</sup>.
Arch. Math. Log., 2005

2004
The proof complexity of linear algebra.
Ann. Pure Appl. Log., 2004

VTC <sup>circ</sup>: A Second-Order Theory for TC<sup>circ</sup>.
Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), 2004

A Second-Order Theory for NL.
Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), 2004

2003
A Complete Axiomatization for Blocks World.
J. Log. Comput., 2003

The importance of the P versus NP question.
J. ACM, 2003

A second-order system for polytime reasoning based on Grädel's theorem.
Ann. Pure Appl. Log., 2003

2002
The optimal location of replicas in a network using a READ-ONE-WRITE-ALL policy.
Distributed Comput., 2002

Complexity Classes, Propositional Proof Systems, and Formal Theories.
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
Electron. Colloquium Comput. Complex., 2001

A Second-Order System for Polytime Reasoning Using Graedel's Theorem.
Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, 2001

2000
Efficiently Approximable Real-Valued Functions
Electron. Colloquium Comput. Complex., 2000

1999
An Exponential Lower Bound for the Size of Monotone Real Circuits.
J. Comput. Syst. Sci., 1999

1998
The Relative Complexity of NP Search Problems.
J. Comput. Syst. Sci., 1998

1997
A Tight Relationship Between Generic Oracles and Type-2 Complexity Theory.
Inf. Comput., 1997

1996
A New Characterization of Type-2 Feasibility.
SIAM J. Comput., 1996

Finding hard instances of the satisfiability problem: A survey.
Proceedings of the Satisfiability Problem: Theory and Applications, 1996

1993
Parallel Pointer Machines.
Comput. Complex., 1993

Functional Interpretations of Feasibly Constructive Arithmetic.
Ann. Pure Appl. Log., 1993

1992
An Optimal Parallel Algorithm for Formula Evaluation.
SIAM J. Comput., 1992

A New Recursion-Theoretic Characterization of the Polytime Functions.
Comput. Complex., 1992

A New Recursion-Theoretic Characterization of the Polytime Functions (Extended Abstract)
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.
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)
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990
A Feasibly Constructive Lower Bound for Resolution Proofs.
Inf. Process. Lett., 1990

1989
Complexity Theory of Parallel Time and Hardware
Inf. Comput., March, 1989

Erratum: Two Applications of Inductive Counting for Complementation Problems.
SIAM J. Comput., 1989

Two Applications of Inductive Counting for Complementation Problems.
SIAM J. Comput., 1989

Functional Interpretations of Feasibly Constructive Arithmetic (Extended Abstract)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Characterizations of the Basic Feasible Functionals of Finite Type (Extended Abstract)
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.
Inf. Process. Lett., 1988

Short Propositional Formulas Represent Nondeterministic Computations.
Inf. Process. Lett., 1988

Two applications of complementation via inductive counting.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987
The Parallel Complexity of Abelian Permutation Group Problems.
SIAM J. Comput., 1987

Problems Complete for Deterministic Logarithmic Space.
J. Algorithms, 1987

1986
Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes.
SIAM J. Comput., 1986

Log Depth Circuits for Division and Related Problems.
SIAM J. Comput., 1986

1985
A Depth-Universal Circuit.
SIAM J. Comput., 1985

A Taxonomy of Problems with Fast Parallel Algorithms
Inf. Control., 1985

1983
The Recognition of Deterministic CFL's in Small Time and Space
Inf. Control., 1983

Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines
Inf. Control., 1983

An Overview of Computational Complexity.
Commun. ACM, 1983

The Parallel Complexity of the Abelian Permutation Group Membership Problem
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

The Classifikation of Problems which have Fast Parallel Algorithms.
Proceedings of the Fundamentals of Computation Theory, 1983

1982
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation.
SIAM J. Comput., 1982

Bounds on the Time for Parallel RAM's to Compute Simple Functions
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

1981
Corrigendum: Soundness and Completeness of an Axiom System for Program Verification.
SIAM J. Comput., 1981

1980
Space Lower Bounds for Maze Threadability on Restricted Machines.
SIAM J. Comput., 1980

Hardware Complexity and Parallel Computation (Preliminary Version)
Proceedings of the 21st Annual Symposium on Foundations of Computer Science, 1980

1979
The Relative Efficiency of Propositional Proof Systems.
J. Symb. Log., 1979

Deterministic CFL's Are Accepted Simultaneously in Polynomial Time and Log Squared Space
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.
SIAM J. Comput., 1978

1976
A short proof of the pigeon hole principle using extended resolution.
SIGACT News, 1976

On the Number of Additions to Compute Specific Polynomials.
SIAM J. Comput., 1976

Storage Requirements for Deterministic Polynomial Time Recognizable Languages.
J. Comput. Syst. Sci., 1976

1975
Proving Assertions about Programs that Manipulate Data Structures
Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

Feasibly Constructive Proofs and the Propositional Calculus (Preliminary Version)
Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

An Assertion Language for Data Structures.
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".
SIGACT News, 1974

An Observation on Time-Storage Trade Off.
J. Comput. Syst. Sci., 1974

On the Lengths of Proofs in the Propositional Calculus (Preliminary Version)
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)
Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

1973
Time Bounded Random Access Machines.
J. Comput. Syst. Sci., 1973

A Hierarchy for Nondeterministic Time Complexity.
J. Comput. Syst. Sci., 1973

1971
Characterizations of Pushdown Machines in Terms of Time-Bounded Computers.
J. ACM, 1971

The Complexity of Theorem-Proving Procedures
Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971

Linear Time Simulation of Deterministic Two-Way Pushdown Automata.
Proceedings of the Information Processing, Proceedings of IFIP Congress 1971, Volume 1, 1971

1970
Path Systems and Language Recognition
Proceedings of the 2nd Annual ACM Symposium on Theory of Computing, 1970

1969
Variations on Pushdown Machines (Detailed Abstract)
Proceedings of the 1st Annual ACM Symposium on Theory of Computing, 1969

1966
The Solvability of the Derivability Problem for One-Normal Systems.
J. ACM, 1966


  Loading...