#2,579

Most Influential Person

American-Canadian computer scientist

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.

- 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:

Stephen Cook is affiliated with the following schools:

This website uses cookies to enhance the user experience. Read the Privacy Policy for more.

Subscribe To Newsletter?Yes!