H-Index & Metrics Best Publications

H-Index & Metrics

Discipline name H-index Citations Publications World Ranking National Ranking
Computer Science D-index 35 Citations 8,938 72 World Ranking 5757 National Ranking 251
Mathematics D-index 39 Citations 20,221 90 World Ranking 1069 National Ranking 42

Research.com Recognitions

Awards & Achievements

2008 - ACM Fellow For fundamental contributions to the theory of computational complexity.

1986 - Fellow of the American Academy of Arts and Sciences

1985 - Member of the National Academy of Sciences

1982 - A. M. Turing Award For his advancement of our understanding of the complexity of computation in a significant and profound way. His seminal paper, "The Complexity of Theorem Proving Procedures," presented at the 1971 ACM SIGACT Symposium on the Theory of Computing, laid the foundations for the theory of NP-Completeness. The ensuing exploration of the boundaries and nature of NP-complete class of problems has been one of the most active and important research activities in computer science for the last decade.

Overview

What is he best known for?

The fields of study he is best known for:

  • Algorithm
  • Programming language
  • Algebra

His primary areas of investigation include Discrete mathematics, Combinatorics, Binary logarithm, Computation and Theoretical computer science. He mostly deals with Polynomial-time reduction in his studies of Discrete mathematics. The study incorporates disciplines such as NP-easy, PP, P versus NP problem, PSPACE-complete and Function problem in addition to Polynomial-time reduction.

The Combinatorics study which covers Function that intersects with Logarithm, Random-access machine, Affine logic and Cobham's thesis. The Binary logarithm study combines topics in areas such as Sorting and Polynomial time complexity. The various areas that Stephen A. Cook examines in his Theoretical computer science study include Asymptotic computational complexity, Computational resource, Worst-case complexity and Average-case complexity.

His most cited work include:

  • The complexity of theorem-proving procedures (5026 citations)
  • The relative efficiency of propositional proof systems (658 citations)
  • A taxonomy of problems with fast parallel algorithms (579 citations)

What are the main themes of his work throughout his whole career to date?

Stephen A. Cook mainly investigates Discrete mathematics, Combinatorics, Complexity class, Function and Time complexity. Stephen A. Cook studies Discrete mathematics, focusing on Binary logarithm in particular. His Combinatorics research is multidisciplinary, relying on both Nondeterministic algorithm and Turing machine.

His Complexity class research focuses on subjects like Bipartite graph, which are linked to Matching. His Function research incorporates themes from Characterization, Limit, Communication complexity, Stack and Corollary. His studies examine the connections between Time complexity and genetics, as well as such issues in Computable function, with regards to Computability.

He most often published in these fields:

  • Discrete mathematics (66.46%)
  • Combinatorics (26.58%)
  • Complexity class (19.62%)

What were the highlights of his more recent work (between 2009-2021)?

  • Discrete mathematics (66.46%)
  • Complexity class (19.62%)
  • Function (16.46%)

In recent papers he was focusing on the following fields of study:

Discrete mathematics, Complexity class, Function, Proof complexity and Algebra are his primary areas of study. He combines subjects such as Mathematical proof, Proof theory and Combinatorics with his study of Discrete mathematics. Stephen A. Cook has researched Combinatorics in several fields, including Nondeterministic algorithm and Binary decision diagram.

His Complexity class study integrates concerns from other disciplines, such as Disjoint sets, Jordan curve theorem and Limit. His Function research also works with subjects such as

  • Conjecture which is related to area like Characterization and Intersection,
  • Stack which intersects with area such as P and Oracle. His research investigates the connection between Proof complexity and topics such as Structural complexity theory that intersect with issues in Computable function.

Between 2009 and 2021, his most popular works were:

  • Logical Foundations of Proof Complexity (124 citations)
  • Complexity Theory for Operators in Analysis (48 citations)
  • Exponential Lower Bounds for Monotone Span Programs (33 citations)

In his most recent research, the most cited papers focused on:

  • Algorithm
  • Programming language
  • Algebra

His primary scientific interests are in Discrete mathematics, Function, Combinatorics, Theoretical computer science and Algebra. He regularly links together related areas like Proof complexity in his Discrete mathematics studies. His Function research includes elements of Communication complexity, Exponential function and Conjecture.

His work carried out in the field of Combinatorics brings together such families of science as Nondeterministic algorithm and Binary decision diagram. The various areas that Stephen A. Cook examines in his Theoretical computer science study include Representation, String, Computational complexity theory and Real number. As a part of the same scientific family, he mostly works in the field of Algebra, focusing on Complexity class and, on occasion, Bipartite graph.

This overview was generated by a machine learning system which analysed the scientist’s body of work. If you have any feedback, you can contact us here.

Best Publications

The complexity of theorem-proving procedures

Stephen A. Cook.
symposium on the theory of computing (1971)

9326 Citations

The relative efficiency of propositional proof systems

Stephen A. Cook;Robert A. Reckhow.
Journal of Symbolic Logic (1979)

1095 Citations

A taxonomy of problems with fast parallel algorithms

Stephen A. Cook.
Information & Computation (1985)

869 Citations

A new recursion-theoretic characterization of the polytime functions

Stephen Bellantoni;Stephen Cook.
Computational Complexity (1992)

624 Citations

SOUNDNESS AND COMPLETENESS OF AN AXIOM SYSTEM FOR PROGRAM VERIFICATION

Stephen A. Cook.
SIAM Journal on Computing (1978)

613 Citations

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. 24–30.

Stephen A. Cook.
Journal of Symbolic Logic (1969)

598 Citations

Time bounded random access machines

Stephen A. Cook;Robert A. Reckhow.
Journal of Computer and System Sciences (1973)

496 Citations

Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

Stephen A. Cook.
Journal of the ACM (1971)

446 Citations

ON THE MINIMUM COMPUTATION TIME OF FUNCTIONS

Stephen A. Cook;Stȧl O. Aanderaa.
Transactions of the American Mathematical Society (1969)

404 Citations

Upper and lower time bounds for parallel random access machines without simultaneous writes

Stephen Cook;Cynthia Dwork;Ru duml;ger Reischuk.
SIAM Journal on Computing (1986)

401 Citations

If you think any of the details on this page are incorrect, let us know.

Contact us

Best Scientists Citing Stephen A. Cook

Toniann Pitassi

Toniann Pitassi

University of Toronto

Publications: 66

Eric Allender

Eric Allender

Rutgers, The State University of New Jersey

Publications: 59

Samuel R. Buss

Samuel R. Buss

University of California, San Diego

Publications: 51

Lance Fortnow

Lance Fortnow

Illinois Institute of Technology

Publications: 43

Pavel Pudlák

Pavel Pudlák

Czech Academy of Sciences

Publications: 41

Avi Wigderson

Avi Wigderson

Institute for Advanced Study

Publications: 37

Rolf Drechsler

Rolf Drechsler

University of Bremen

Publications: 36

Oscar H. Ibarra

Oscar H. Ibarra

University of California, Santa Barbara

Publications: 35

Paul Beame

Paul Beame

University of Washington

Publications: 35

Marek Karpinski

Marek Karpinski

University of Bonn

Publications: 31

Christos H. Papadimitriou

Christos H. Papadimitriou

Columbia University

Publications: 30

Leslie G. Valiant

Leslie G. Valiant

Harvard University

Publications: 30

Alan L. Selman

Alan L. Selman

University at Buffalo, State University of New York

Publications: 29

Russell Impagliazzo

Russell Impagliazzo

University of California, San Diego

Publications: 28

Joao Marques-Silva

Joao Marques-Silva

Centre national de la recherche scientifique, CNRS

Publications: 27

Eli Ben-Sasson

Eli Ben-Sasson

Technion – Israel Institute of Technology

Publications: 26

Something went wrong. Please try again later.