Stephen Cook
#667
Most Influential Person
American-Canadian computer scientist
Stephen Cook's AcademicInfluence.com Rankings
Computer Science
#75
World Rank
#80
Historical Rank
#43
USA Rank
Theoretical Computer Science
#7
World Rank
#7
Historical Rank
#5
USA Rank
Database
#322
World Rank
#356
Historical Rank
#144
USA Rank
Why Is Stephen Cook Influential?
(Suggest an Edit or Addition)According to Wikipedia, Stephen Arthur Cook is an American-Canadian computer scientist and mathematician who has made significant 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) (6861)
- The relative efficiency of propositional proof systems (1979) (956)
- A Taxonomy of Problems with Fast Parallel Algorithms (1985) (657)
- Review: Alan Cobham, Yehoshua Bar-Hillel, The Intrinsic Computational Difficulty of Functions (1969) (562)
- Soundness and Completeness of an Axiom System for Program Verification (1978) (499)
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers (1971) (362)
- A new recursion-theoretic characterization of the polytime functions (1992) (346)
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes (1986) (330)
- Log Depth Circuits for Division and Related Problems (1984) (328)
- ON THE MINIMUM COMPUTATION TIME OF FUNCTIONS (1969) (320)
- An observation on time-storage trade off (1973) (270)
- Finding hard instances of the satisfiability problem: A survey (1996) (266)
- Time-bounded random access machines (1972) (266)
- Feasibly constructive proofs and the propositional calculus (Preliminary Version) (1975) (234)
- On the lengths of proofs in the propositional calculus (Preliminary Version) (1974) (208)
- A hierarchy for nondeterministic time complexity (1972) (188)
- The P versus NP Problem (2010) (174)
- Functional interpretations of feasibly constructive arithmetic (1989) (168)
- The relative complexity of NP search problems (1995) (168)
- Problems Complete for Deterministic Logarithmic Space (1987) (160)
- Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines (1984) (156)
- A time-space tradeoff for sorting on a general sequential model of computation (1980) (155)
- Logical Foundations of Proof Complexity (2010) (144)
- Two Applications of Inductive Counting for Complementation Problems (1989) (142)
- Time Bounded Random Access Machines (1973) (138)
- Deterministic CFL's are accepted simultaneously in polynomial time and log squared space (1979) (130)
- Space Lower Bounds for Maze Threadability on Restricted Machines (1980) (113)
- Computing over the Reals: Foundations for Scientific Computing (2005) (108)
- Linear Time Simulation of Deterministic Two-Way Pushdown Automata (1971) (101)
- An Optimal Parallel Algorithm for Formula Evaluation (1992) (99)
- A New Characterization of Type-2 Feasibility (1996) (96)
- A short proof of the pigeon hole principle using extended resolution (1976) (92)
- Storage Requirements for Deterministic Polynomial Time Recognizable Languages (1976) (91)
- Hardware complexity and parallel computation (1980) (90)
- Logical Foundations of Proof Complexity: INDEX (2010) (90)
- An overview of computational complexity (1983) (90)
- An Exponential Lower Bound for the Size of Monotone Real Circuits (1999) (87)
- Complexity Theory for Operators in Analysis (2012) (82)
- A new recursion-theoretic characterization of the polytime functions (extended abstract) (1992) (80)
- Storage requirements for deterministic / polynomial time recognizable languages (1974) (79)
- On the Number of Additions to Compute Specific Polynomials (1976) (76)
- Short Propositional Formulas Represent Nondeterministic Computations (1988) (76)
- Bounds on the time for parallel RAM's to compute simple functions (1982) (75)
- Consequences of the provability of NP ⊆ P/poly (2007) (71)
- Exponential Lower Bounds for Monotone Span Programs (2016) (71)
- Quantified propositional calculus and a second-order theory for NC1 (2005) (70)
- Computability and Complexity of Higher Type Functions (1992) (67)
- The proof complexity of linear algebra (2002) (66)
- Characterizations of the basic feasible functionals of finite type (1989) (61)
- The Classifikation of Problems which have Fast Parallel Algorithms (1983) (58)
- The strength of replacement in weak arithmetic (2004) (58)
- Boolean programs and quantified propositional proof systems (1999) (50)
- The importance of the P versus NP question (2003) (49)
- Complexity Theory of Parallel Time and Hardware (1989) (40)
- The optimal location of replicas in a network using a READ-ONE-WRITE-ALL policy (2002) (40)
- The Parallel Complexity of Abelian Permutation Group Problems (1987) (39)
- Theories for complexity classes and their propositional translations (2004) (38)
- A Depth-Universal Circuit (1985) (35)
- Path systems and language recognition (1970) (34)
- Proving assertions about programs that manipulate data structures (1975) (33)
- Two applications of complementation via inductive counting (1988) (32)
- Computational complexity of higher type functions (1990) (28)
- An assertion language for data structures (1975) (28)
- Pebbles and Branching Programs for Tree Evaluation (2010) (26)
- The complexity of derivations of matrix identities (2001) (25)
- The Hardness of Being Private (2012) (25)
- A Complete Axiomatization for Blocks World (2003) (24)
- The parallel complexity of the abelian permutation group membership problem (1983) (23)
- Theories for TC0 and Other Small Complexity Classes (2005) (23)
- Corrections for "On the lengths of proofs in the propositional calculus preliminary version" (1974) (22)
- 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)
- A second-order system for polytime reasoning based on Grädel's theorem (2003) (21)
- The Recognition of Deterministic CFL's in Small Time and Space (1983) (20)
- A new characterization of Mehlhorn's polynomial time functionals (1991) (20)
- Lower bounds in parallel machine computation (1987) (17)
- Efficiently Approximable Real-Valued Functions (2000) (17)
- A Simple Parallel Algorithm for Finding a Satisfying Truth Assignment to a 2-CNF Formula (1988) (16)
- A Tight Relationship Between Generic Oracles and Type-2 Complexity Theory (1997) (15)
- Corrigendum: Soundness and Completeness of an Axiom System for Program Verification (1981) (14)
- The complexity of the comparator circuit value problem (2012) (14)
- Relating the provable collapse of P to NC1 and the power of logical theories (1996) (14)
- A second-order theory for NL (2004) (13)
- Average Case Lower Bounds for Monotone Switching Networks (2013) (13)
- A Feasibly Constructive Lower Bound for Resolution Proofs (1990) (12)
- Formal Theories for Linear Algebra (2010) (11)
- Complexity theory for operators in analysis (2010) (11)
- Parallel pointer machines (2005) (11)
- Parallel Computation for Well-Endowed Rings (1983) (9)
- Functional Interpretations of Feasibly Constructive Arithmetic (Extended Abstract) (1989) (9)
- Relativizing small complexity classes and their theories (2007) (9)
- Branching Programs for Tree Evaluation (2009) (9)
- Mathematical Foundations of Computer Science 2009 (2009) (8)
- The Solvability of the Derivability Problem for One-Normal Systems (1966) (8)
- Variations on pushdown machines (Detailed Abstract) (1969) (7)
- Erratum: Two Applications of Inductive Counting for Complementation Problems (1989) (7)
- Formalizing Randomized Matching Algorithms (2011) (7)
- Fractional Pebbling and Thrifty Branching Programs (2009) (6)
- VTC: A Second-Order Theory for TC (2004) (6)
- A second-order system for polytime reasoning using Gradel's theorem (2001) (6)
- A Formal Theory for the Complexity Class Associated with the Stable Marriage Problem (2011) (5)
- The Complexity of Proving the Discrete Jordan Curve Theorem (2007) (5)
- Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs (2016) (5)
- Uniform, integral and efficient proofs for the determinant identities (2017) (4)
- On the number of additions to compute specific polynomials (Preliminary Version) (1974) (4)
- The Log Space Oracle Hierarchy Collapses DRAFT (1987) (4)
- Computational complexity of higher type functions : plenary address, International Congress of Mathematicians Kyoto, Japan August, 1990 (1990) (3)
- Eeciently Approximable Real-valued Functions (2000) (3)
- The Complexity of Theorem-Proving Procedures (1971) (2021) (3)
- Logical Foundations of Proof Complexity: INTRODUCTION (2010) (3)
- The optimal placement of replicas in a network using a read any - write all policy (1992) (3)
- Review: Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions (1969) (3)
- A second-order system for polynomial-time reasoning based on Graedel's theorem (2001) (3)
- Hardware Complexity and Parallel Computation (Preliminary Version) (1980) (2)
- Connecting Complexity Classes, Weak Formal Theories, and Propositional Proof Systems (Invited Talk) (2012) (1)
- Theories for Subexponential-size Bounded-depth Frege Proofs (2013) (1)
- Complexity Classes and Theories for the Comparator Circuit Value Problem (2011) (1)
- Functional Interpretations of Feasibly Constructive Arithmetic Abstract (1990) (1)
- VTC circ: A Second-Order Theory for TCcirc (2004) (1)
- Relativized Propositional Calculus (2012) (1)
- 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) (1)
- Logical Foundations of Proof Complexity: PEANO ARITHMETIC AND ITS SUBSYSTEMS (2010) (1)
- JSL volume 49 issue 4 Cover and Back matter and Errata (1984) (0)
- JSL volume 52 issue 4 Cover and Back matter and Errata (1987) (0)
- The Achievements and Challenges of Computational Complexity (1999) (0)
- The Tree Evaluation Problem : Towards Separating P from NL Lecture # 6 : 26 February 2014 (2014) (0)
- A Survey of Classes of Primitive Recursive Functions (2017) (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)
- And Other Small Complexity Classes (2008) (0)
- Logical Foundations of Proof Complexity: PROOF SYSTEMS AND THE REFLECTION PRINCIPLE (2010) (0)
- Logical Foundations of Proof Complexity: THE THEORY V 1 AND POLYNOMIAL TIME (2010) (0)
- Comments on Beckmann's Uniform Reducts (2006) (0)
- The Turing Computational Model (2012) (0)
- Explorer Fractional Pebbling and Thrifty Branching Programs (2015) (0)
- Recent Advances in Complexity Theory (2006) (0)
- Advances in Complexity Theory (2004) (0)
- Computational Complexity ( 10 w 5028 ) (2011) (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)
- Leibniz International Proceedings in Informatics Fractional Pebbling and Thrifty Branching Programs (2009) (0)
- THEORIES FOR SMALL CLASSES (2010) (0)
- Logical Foundations of Proof Complexity: TWO-SORTED LOGIC AND COMPLEXITY CLASSES (2010) (0)
- JSL volume 50 issue 4 Cover and Back matter and Errata (1985) (0)
- Complexity Classes, Propositional Proof Systems, and Formal Theories (2002) (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)
- THE PREDICATE CALCULUS AND THE SYSTEM LK (2010) (0)
- Review: Jiri Becvar, Real-Time and Complexity Problems in Automata Theory (1971) (0)
- THEORIES FOR POLYNOMIAL TIME AND BEYOND (2010) (0)
- Logical Foundations of Computer Science (2013) (0)
- Uniform, Integral, and Feasible Proofs for the Determinant Identities (2018) (0)
- A Complete Axiomatization for Blo ks World (2007) (0)
- Logical Foundations of Proof Complexity: THE THEORY V 0 AND AC 0 (2010) (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:
