Stephen A. Cook
According to our database^{1},
Stephen A. Cook
authored at least 118 papers
between 1966 and 2017.
Collaborative distances:
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 OtherLinks
Homepages:

at zbmath.org

at viaf.org

at isni.org

at id.loc.gov

at dnb.info

at andrej.com

at dl.acm.org
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 ReadOnce 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 Subexponentialsize Boundeddepth 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 NP ⊆ P/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 secondorder theory for NC^{1}.
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 SecondOrder Theory for TC^{circ}.
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 SecondOrder 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 secondorder 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 READONEWRITEALL 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 secondorder system for polynomialtime reasoning based on Graedel's theorem
Electronic Colloquium on Computational Complexity (ECCC), 2001
A SecondOrder System for Polytime Reasoning Using Graedel's Theorem.
Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, 2001
2000
Efficiently Approximable RealValued 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 Type2 Complexity Theory.
Inf. Comput., 1997
1996
A New Characterization of Type2 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 TwentySeventh 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 RecursionTheoretic Characterization of the Polytime Functions.
Computational Complexity, 1992
A New RecursionTheoretic 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 2CNF 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 DepthUniversal 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 WellEndowed Rings and SpaceBounded 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 TimeSpace 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 TimeSpace 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 TimeStorage 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 TimeStorage Trade Off
Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30, 1973
1972
TimeBounded 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 TimeBounded Computers.
J. ACM, 1971
The Complexity of TheoremProving Procedures
Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971
Linear Time Simulation of Deterministic TwoWay 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 OneNormal Systems.
J. ACM, 1966