Stephen A. Cook

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

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 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2017
A Survey of Classes of Primitive Recursive Functions.
Electronic Colloquium on Computational Complexity (ECCC), 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.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Relativizing small complexity classes and their theories.
Computational Complexity, 2016

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

Exponential Lower Bounds for Monotone Span Programs.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2014
The complexity of the comparator circuit value problem.
TOCT, 2014

The Hardness of Being Private.
TOCT, 2014

2013
Average Case Lower Bounds for Monotone Switching Networks.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Complexity Theory for Operators in Analysis
CoRR, 2013

Average Case Lower Bounds for Monotone Switching Networks.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 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.
TOCT, 2012

Pebbles and Branching Programs for Tree Evaluation.
TOCT, 2012

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

The Complexity of the Comparator Circuit Value Problem
CoRR, 2012

Relativizing Small Complexity Classes and their Theories
CoRR, 2012

Relativized Propositional Calculus
CoRR, 2012

Formal Theories for Linear Algebra
Logical Methods in Computer Science, 2012

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

The Hardness of Being Private.
Proceedings of the 27th Conference on Computational Complexity, 2012

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

Formalizing Randomized Matching Algorithms
Logical Methods in Computer Science, 2011

Formalizing Randomized Matching Algorithms.
Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science, 2011

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

2010
Pebbles and Branching Programs for Tree Evaluation
CoRR, 2010

The Complexity of Proving the Discrete Jordan Curve Theorem
CoRR, 2010

Complexity theory for operators in analysis.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Formal Theories for Linear Algebra.
Proceedings of the Computer Science Logic, 24th International Workshop, 2010

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 NPP/poly.
J. Symb. Log., 2007

The Complexity of Proving the Discrete Jordan Curve Theorem.
Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), 2007

Relativizing Small Complexity Classes and Their Theories.
Proceedings of the Computer Science Logic, 21st International Workshop, 2007

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

Theories for TC0 and Other Small Complexity Classes.
Logical Methods in Computer Science, 2006

Comments on Beckmann's Uniform Reducts
CoRR, 2006

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

Theories for TC0 and Other Small Complexity Classes
CoRR, 2005

Quantified propositional calculus and a second-order theory for NC1.
Arch. Math. Log., 2005

2004
The strength of replacement in weak arithmetic
CoRR, 2004

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

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

The Strength of Replacement in Weak Arithmetic.
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. Logic, 2003

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

The Proof Complexity of Linear Algebra.
Proceedings of the 17th IEEE Symposium on Logic in Computer Science (LICS 2002), 2002

Complexity Classes, Propositional Proof Systems, and Formal Theories.
Proceedings of the 17th IEEE Symposium on Logic in Computer Science (LICS 2002), 2002

A Complete Axiomatization for Blocks World.
Proceedings of the International Symposium on Artificial Intelligence and Mathematics, 2002

2001
A second-order system for polynomial-time reasoning based on Graedel's theorem
Electronic Colloquium on Computational Complexity (ECCC), 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
Electronic Colloquium on Computational Complexity (ECCC), 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

1995
The relative complexity of NP search problems.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

1993
Parallel Pointer Machines.
Computational Complexity, 1993

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

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

A New Recursion-Theoretic Characterization of the Polytime Functions.
Computational Complexity, 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
Information and Control, 1985

1984
Log Depth Circuits for Division and Related Problems
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

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

Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines
Information and 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

A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 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
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
An Observation on Time-Storage Trade Off.
J. Comput. Syst. Sci., 1974

Storage Requirements for Deterministic Polynomial Time Recognizable Languages
Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 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

An Observation on Time-Storage Trade Off
Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30, 1973

1972
Time-Bounded Random Access Machines
Proceedings of the 4th Annual ACM Symposium on Theory of Computing, 1972

A Hierarchy for Nondeterministic Time Complexity
Proceedings of the 4th Annual ACM Symposium on Theory of Computing, 1972

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.
IFIP Congress (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...