Stephen Cook | Academic Influence

Why Is Stephen Cook Influential?

According to Wikipedia, Stephen Arthur Cook, is an American-Canadian computer scientist and mathematician who has made major contributions to the fields of complexity theory and proof complexity. He is a university professor at the University of Toronto, Department of Computer Science and Department of Mathematics.

Stephen Cook's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Papers

The complexity of theorem-proving procedures (1971) (6624)
The Relative Efficiency of Propositional Proof Systems (1979) (946)
A Taxonomy of Problems with Fast Parallel Algorithms (1985) (690)
Soundness and Completeness of an Axiom System for Program Verification (1978) (491)
Characterizations of Pushdown Machines in Terms of Time-Bounded Computers (1971) (375)
Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes (1986) (355)
A new recursion-theoretic characterization of the polytime functions (2005) (331)
ON THE MINIMUM COMPUTATION TIME OF FUNCTIONS (1969) (293)
Time-bounded random access machines (1972) (254)
Finding hard instances of the satisfiability problem: A survey (1996) (254)
Feasibly constructive proofs and the propositional calculus (Preliminary Version) (1975) (222)
Log Depth Circuits for Division and Related Problems (1986) (208)
An observation on time-storage trade off (1973) (196)
Problems Complete for Deterministic Logarithmic Space (1987) (163)
Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines (1983) (154)
Two Applications of Inductive Counting for Complementation Problems (1989) (152)
The P versus NP Problem (2010) (149)
Time Bounded Random Access Machines (1973) (145)
Deterministic CFL's are accepted simultaneously in polynomial time and log squared space (1979) (137)
A hierarchy for nondeterministic time complexity (1972) (136)
Log Depth Circuits for Division and Related Problems (1984) (127)
Space Lower Bounds for Maze Threadability on Restricted Machines (1980) (124)
A time-space tradeoff for sorting on a general sequential model of computation (1980) (124)
Functional interpretations of feasibly constructive arithmetic (1989) (122)
An Observation on Time-Storage Trade Off (1974) (114)
Logical Foundations of Proof Complexity: INDEX (2010) (109)
Logical Foundations of Proof Complexity (2010) (107)
Linear Time Simulation of Deterministic Two-Way Pushdown Automata (1971) (105)
An Optimal Parallel Algorithm for Formula Evaluation (1992) (105)
Storage Requirements for Deterministic Polynomial Time Recognizable Languages (1976) (102)
Computing over the Reals: Foundations for Scientific Computing (2005) (99)
The Relative Complexity of NP Search Problems (1998) (98)
A New Characterization of Type-2 Feasibility (1996) (94)
An Exponential Lower Bound for the Size of Monotone Real Circuits (1999) (90)
A new recursion-theoretic characterization of the polytime functions (extended abstract) (1992) (89)
Hardware complexity and parallel computation (1980) (89)
An overview of computational complexity (1983) (88)
A short proof of the pigeon hole principle using extended resolution (1976) (84)
Short Propositional Formulas Represent Nondeterministic Computations (1988) (82)
Bounds on the time for parallel RAM's to compute simple functions (1982) (80)
The relative complexity of NP search problems (1995) (77)
On the Number of Additions to Compute Specific Polynomials (1976) (74)
Quantified propositional calculus and a second-order theory for NC1 (2005) (72)
Consequences of the provability of NP ⊆ P/poly (2007) (69)
Exponential Lower Bounds for Monotone Span Programs (2016) (69)
Computability and Complexity of Higher Type Functions (1992) (66)
A Hierarchy for Nondeterministic Time Complexity (1973) (66)
Storage requirements for deterministic / polynomial time recognizable languages (1974) (66)
Complexity Theory for Operators in Analysis (2012) (63)
The proof complexity of linear algebra (2004) (61)
The Classifikation of Problems which have Fast Parallel Algorithms (1983) (59)
Characterizations of the basic feasible functionals of finite type (1989) (58)
Functional Interpretations of Feasibly Constructive Arithmetic (1993) (58)
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation (1982) (54)
Boolean programs and quantified propositional proof systems (1999) (52)
The strength of replacement in weak arithmetic (2004) (51)
The importance of the P versus NP question (2003) (46)
The Parallel Complexity of Abelian Permutation Group Problems (1987) (41)
Complexity Theory of Parallel Time and Hardware (1989) (39)
The optimal location of replicas in a network using a READ-ONE-WRITE-ALL policy (2002) (39)
Theories for complexity classes and their propositional translations (2004) (39)
Path systems and language recognition (1970) (37)
Two applications of complementation via inductive counting (1988) (35)
A Depth-Universal Circuit (1985) (35)
Proving assertions about programs that manipulate data structures (1975) (34)
Computational complexity of higher type functions (1990) (29)
An assertion language for data structures (1975) (28)
The complexity of derivations of matrix identities (2001) (27)
The parallel complexity of the abelian permutation group membership problem (1983) (25)
Pebbles and Branching Programs for Tree Evaluation (2012) (23)
The Hardness of Being Private (2012) (23)
Corrections for "On the lengths of proofs in the propositional calculus preliminary version" (1974) (23)
Cobham Alan. The intrinsic computational difficulty of functions. Logic, methodology and philosophy of science, Proceedings of the 1964 International Congress , edited by Bar-Hillel Yehoshua, Studies in logic and the foundations of mathematics, North-Holland Publishing Company, Amsterdam 1965, pp. 2 (1969) (22)
Complexity theory for operators in analysis (2010) (22)
A second-order system for polytime reasoning based on Grädel's theorem (2003) (22)
A Complete Axiomatization for Blocks World (2002) (20)
The Recognition of Deterministic CFL's in Small Time and Space (1983) (19)
Lower bounds in parallel machine computation (1987) (19)
Efficiently Approximable Real-Valued Functions (2000) (18)
Theories for TC0 and Other Small Complexity Classes (2006) (18)
On the complexity of proof systems (1996) (18)
A Simple Parallel Algorithm for Finding a Satisfying Truth Assignment to a 2-CNF Formula (1988) (17)
A Tight Relationship Between Generic Oracles and Type-2 Complexity Theory (1997) (17)
A new characterization of Mehlhorn's polynomial time functionals (1991) (17)
Corrigendum: Soundness and Completeness of an Axiom System for Program Verification (1981) (15)
The complexity of the comparator circuit value problem (2014) (14)
Relating the provable collapse of P to NC1 and the power of logical theories (1996) (13)
Average Case Lower Bounds for Monotone Switching Networks (2013) (13)
A Feasibly Constructive Lower Bound for Resolution Proofs (1990) (12)
Parallel Computation for Well-Endowed Rings (1983) (12)
Formal Theories for Linear Algebra (2012) (11)
The proof complexity of linear algebra (2002) (10)
Parallel pointer machines (2005) (10)
Functional Interpretations of Feasibly Constructive Arithmetic (Extended Abstract) (1989) (9)
The strength of replacement in weak arithmetic (2004) (9)
Mathematical Foundations of Computer Science 2009 (2009) (8)
Branching Programs for Tree Evaluation (2009) (8)
A second-order theory for NL (2004) (7)
Variations on pushdown machines (Detailed Abstract) (1969) (7)
A second-order system for polytime reasoning using Gradel's theorem (2001) (7)
The Solvability of the Derivability Problem for One-Normal Systems (1966) (7)
Erratum: Two Applications of Inductive Counting for Complementation Problems (1989) (7)
Formalizing Randomized Matching Algorithms (2011) (6)
Logical Foundations of Proof Complexity: INTRODUCTION (2010) (6)
Average case computational complexity theory (1997) (6)
VTC: A Second-Order Theory for TC (2004) (6)
The Complexity of Proving the Discrete Jordan Curve Theorem (2007) (5)
A Formal Theory for the Complexity Class Associated with the Stable Marriage Problem (2011) (5)
Fractional Pebbling and Thrifty Branching Programs (2009) (5)
The Hardness of Being Private (2012) (5)
Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs (2016) (5)
Relativizing small complexity classes and their theories (2015) (4)
Uniform, integral and efficient proofs for the determinant identities (2017) (4)
Relativizing Small Complexity Classes and Their Theories (2007) (4)
A second-order theory for NL (2004) (4)
Eeciently Approximable Real-valued Functions (2000) (3)
The optimal placement of replicas in a network using a read any - write all policy (1992) (3)
Review: Alan Cobham, Yehoshua Bar-Hillel, The Intrinsic Computational Difficulty of Functions (1969) (3)
Computational complexity of higher type functions : plenary address, International Congress of Mathematicians Kyoto, Japan August, 1990 (1990) (3)
On the number of additions to compute specific polynomials (Preliminary Version) (1974) (3)
Logical Foundations of Proof Complexity: PEANO ARITHMETIC AND ITS SUBSYSTEMS (2010) (3)
The Log Space Oracle Hierarchy Collapses DRAFT (1987) (2)
Formal Theories for Linear Algebra (2010) (2)
A second-order system for polynomial-time reasoning based on Graedel's theorem (2001) (2)
VTC circ: A Second-Order Theory for TCcirc (2004) (2)
Theories for Subexponential-size Bounded-depth Frege Proofs (2013) (2)
Review: Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions (1969) (2)
Complexity Classes and Theories for the Comparator Circuit Value Problem (2011) (1)
The Complexity of Proving the Discrete Jordan Curve Theorem (2007) (1)
Hardware Complexity and Parallel Computation (Preliminary Version) (1980) (1)
An overview of computational complexity (2007) (1)
Relativized Propositional Calculus (2012) (1)
Comments on Beckmann's Uniform Reducts (2006) (0)
Functional Interpretations of Feasibly Constructive Arithmetic Abstract (1990) (0)
The Achievements and Challenges of Computational Complexity (1999) (0)
VTC/sup O/: a second-order theory for TC/sup 0/ (2004) (0)
And Other Small Complexity Classes (2008) (0)
Advances in Complexity Theory (2004) (0)
Uniform, Integral, and Feasible Proofs for the Determinant Identities (2018) (0)
The Complexity of Theorem-Proving Procedures (1971) (2021) (0)
A Survey of Classes of Primitive Recursive Functions (2017) (0)
The Tree Evaluation Problem : Towards Separating P from NL Lecture # 6 : 26 February 2014 (2014) (0)
Complexity Classes, Propositional Proof Systems, and Formal Theories (2002) (0)
Logical Foundations of Proof Complexity: TWO-SORTED LOGIC AND COMPLEXITY CLASSES (2010) (0)
THEORIES FOR POLYNOMIAL TIME AND BEYOND (2010) (0)
Review: Jan Krajicek, Pavel Pudlak, Gaisi Takeuti, Bounded Arithmetic and the Polynomial Hierarchy; Samuel R. Buss, Relating the Bounded Arithmetic and Polynomial Time Hierarchies; Domenico Zambella, Notes on Polynomially Bounded Arithmetic (1999) (0)
Mathematisches Forschungsinstitut Oberwolfach Proving Hard-core Predicates Using List Decoding Proving Integrality Gaps without Knowing the Linear Program How to Go beyond the Black-box Simulation Barrier Derandomization in Cryptography Formula Caching Proof Systems Algebras of Minimal Rank over Arb (2003) (0)
Connecting Complexity Classes, Weak Formal Theories, and Propositional Proof Systems (Invited Talk) (2012) (0)
Logical Foundations of Proof Complexity: THE THEORY V 1 AND POLYNOMIAL TIME (2010) (0)
THE PREDICATE CALCULUS AND THE SYSTEM LK (2010) (0)
The Turing Computational Model (2012) (0)
Recent Advances in Complexity Theory (2006) (0)
A Complete Axiomatization for Blo ks World (2007) (0)
The Strength of Replacement in Weak Arithmetic (2004) (0)
Computational Complexity ( 10 w 5028 ) (2011) (0)
Logical Foundations of Proof Complexity: THE THEORY V 0 AND AC 0 (2010) (0)
Review: Jiri Becvar, Real-Time and Complexity Problems in Automata Theory (1971) (0)
Explorer Fractional Pebbling and Thrifty Branching Programs (2015) (0)
THEORIES FOR SMALL CLASSES (2010) (0)
Formalizing Randomized Matching Algorithms (2011) (0)
Leibniz International Proceedings in Informatics Fractional Pebbling and Thrifty Branching Programs (2009) (0)
Bečvář Jiří. Real-time and complexity problems in automata theory. English with Czech summary. Kybernetika (Prague), vol. 1 (1965), pp. 475–498. (1971) (0)
Blum Manuel. A Machine-independent theory of the complexity of recursive functions. Journal of the Association for Computing Machinery, vol. 14 (1967), pp. 322–336. (1969) (0)
Logical Foundations of Proof Complexity: PROOF SYSTEMS AND THE REFLECTION PRINCIPLE (2010) (0)
Logical Foundations of Computer Science (2013) (0)

This paper list is powered by the following services:

Other Resources About Stephen Cook

What Schools Are Affiliated With Stephen Cook?

Stephen Cook is affiliated with the following schools:

Stephen Cook's AcademicInfluence.com Rankings

Computer Science

Image Attributions

Image Source for Stephen Cook