# Richard E. Stearns

#4,573

Most Influential Person Now

American computer scientist

## Richard E. Stearns's AcademicInfluence.com Rankings

Richard E. Stearnscomputer-science Degrees

Computer Science

#481

World Rank

#499

Historical Rank

#267

USA Rank

Database

#1990

World Rank

#2088

Historical Rank

#475

USA Rank

## Download Badge

Computer Science

## Richard E. Stearns's Degrees

- PhD Computer Science University of California, Berkeley
- Masters Computer Science University of California, Berkeley

## Similar Degrees You Can Earn

## Why Is Richard E. Stearns Influential?

(Suggest an Edit or Addition)According to Wikipedia, Richard Edwin Stearns is an American computer scientist who, with Juris Hartmanis, received the 1993 ACM Turing Award "in recognition of their seminal paper which established the foundations for the field of computational complexity theory". In 1994 he was inducted as a Fellow of the Association for Computing Machinery.

## Richard E. Stearns's Published Works

### Published Works

- On the Computational Complexity of Algorithms (1965) (987)
- An Analysis of Several Heuristics for the Traveling Salesman Problem (1977) (955)
- Algebraic Structure Theory Of Sequential Machines (1966) (610)
- Syntax-Directed Transduction (1966) (390)
- System level concurrency control for distributed database systems (1978) (381)
- Hierarchies of memory limited computations (1965) (346)
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs (1998) (319)
- Two-Tape Simulation of Multitape Turing Machines (1966) (272)
- Memory bounds for recognition of context-free and context-sensitive languages (1965) (212)
- The Voting Problem (1959) (159)
- Attributed Translations (1974) (153)
- Properties of Deterministic Top-Down Grammars (1970) (143)
- Approximate Algorithms for the Traveling Salesperson Problem (1974) (136)
- Convergent transfer schemes for $N$-person games (1968) (122)
- Properties of deterministic top down grammars (1969) (119)
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata (1985) (116)
- Compiler design theory (1976) (115)
- A Regularity Test for Pushdown Machines (1967) (104)
- Distributed database concurrency controls using before-values (1981) (104)
- The Complexity of Planar Counting Problems (1998) (100)
- Complexity of reachability problems for finite discrete dynamical systems (2006) (84)
- Concurrency control for database systems (1976) (73)
- Gardens of Eden and Fixed Points in Sequential Dynamical Systems (2001) (68)
- Reachability problems for sequential dynamical systems with threshold functions (2003) (64)
- Predecessor existence problems for finite discrete dynamical systems (2007) (55)
- Pair Algebra and Its Application to Automata Theory (1964) (54)
- Some Dangers in State Reduction of Sequential Machines (1962) (47)
- Regularity Preserving Modifications of Regular Expressions (1963) (45)
- On the equivalence and containment problems for unambiguous regular expressions, grammars, and automata (1981) (45)
- A Unified Approach to Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs (1994) (44)
- Predecessor and Permutation Existence Problems for Sequential Dynamical Systems (2003) (37)
- On the State Assignment Problem for Sequential Machines II (1961) (37)
- The Complexity of Equivalence for Commutative Rings (1990) (36)
- On the Complexity of Relational Problems for Finite State Processes (Extended Abstract) (1996) (34)
- Property Grammars and Table Machines (1968) (29)
- The Complexity of Very Simple Boolean Formulas with Applications (1990) (28)
- Power indices and easier hard problems (1990) (26)
- Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems (2011) (24)
- An Algebraic Model for Combinatorial Problems (1996) (22)
- A Study of Feedback and Errors in Sequential Machines (1963) (21)
- Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems (1998) (21)
- Generalized CNF satisfiability problems and non-efficient approximability (1994) (20)
- On Some Special Classes of Sequential Dynamical Systems (2003) (20)
- Turing Award lecture: it's time to reconsider time (1994) (19)
- Analysis Problems for Sequential Dynamical Systems and Communicating State Machines (2001) (17)
- Computational complexity of recursive sequences (1964) (17)
- Computational Aspects of Analyzing Social Network Dynamics (2007) (16)
- The polynomial time decidability of simulation relations for finite processes: A HORNSAT based approach (1996) (15)
- Complexity of hierarchically and 1-dimensional periodically specified problems I: Hardness results (1995) (14)
- Monotone Boolean Formulas, Distributive Lattices, and the Complexities of Logics, Algebraic Structures, and Computation Structures (Preliminary Report) (1986) (13)
- Analysis Problems for Graphical Dynamical Systems: A Unified Approach Through Graph Predicates (2015) (13)
- Attributed translations(Extended Abstract) (1973) (12)
- Inferring local transition functions of discrete dynamical systems from observations of system behavior (2017) (12)
- Approximation Schemes Using L-Reductions (1994) (11)
- Theory of periodically specified problems: complexity and approximability (1997) (11)
- Efficient Algorithms for Solving Systems of Linear Equations and Path Problems (1992) (11)
- Table Machine Simulation (1969) (9)
- Errata for the paper "Predecessor existence problems for finite discrete dynamical systems" [TCS 386 (1-2) (2007) 3-37] (2008) (9)
- Juris Hartmanis: the beginnings of computational complexity (1988) (9)
- On the axioms for a cooperative game without side payments (1964) (8)
- Testing Phase Space Properties of Synchronous Dynamical Systems with Nested Canalyzing Local Functions (2018) (7)
- Learning the Behavior of a Dynamical System Via a "20 Questions" Approach (2018) (7)
- Parallel Approximation Schemes for a Class of Planar and Near Planar Combinatorial Optimization Problems (2002) (7)
- Approximation schemes for PSPACE-complete problems for succinct specifications (preliminary version) (1994) (7)
- NP-Complete Problems (2019) (6)
- Consistency and Serializability in Concurrent Database Systems (1984) (6)
- Nonlinear Algebra and Optimization on Rings are "Hard" (1987) (6)
- Symmetry Properties of Nested Canalyzing Functions (2019) (6)
- Automata-based computational complexity (1969) (5)
- Fundamental limitations on efficiently forecasting certain epidemic measures in network models (2022) (5)
- Polynomial Time Mechanisms for Collective Decision Making (2000) (5)
- Strongly-local reductions and the complexity/efficient approximability of algebra and optimization on abstract algebraic structures (2001) (5)
- On finite strategy sets for finitely repeated zero-sum games (2003) (5)
- Level-treewidth property, exact algorithms and approximation schemes (1997) (5)
- Efficient Algorithms for δ-Near-Planar Graph and Algebraic Problems (1993) (4)
- The Hughes site, an aboriginal village site on the Potomac River in Montgomery County, Maryland (1940) (4)
- Complexity and Approximability of Quantified and Stochastic Constraint Satisfaction Problems (2001) (4)
- 19. Three-Person Cooperative Games Without Side Payments (1964) (4)
- Exploiting structure in quantified formulas (2002) (3)
- Towards syntactic characterizations of approximation schemes via predicate and graph decompositions (1998) (3)
- Bounded rationality in repeated games and mechanism design for agents in computational settings (2000) (3)
- Deterministic versus nondeterministic time and lower bound problems (2003) (3)
- Bounds and Complexity Results for Learning Coalition-Based Interaction Functions in Networked Social Systems (2020) (3)
- Generalized CNF satisfiability, local reductions and complexity of succinctly specified problems (1995) (2)
- Inferring Probabilistic Contagion Models Over Networks Using Active Queries (2018) (2)
- The Development of a General Model for Estimating Computer Search Time for CA Condensates (1970) (2)
- Computational Complexity of Analyzing the Dynamic Reliability of Interdependent Infrastructures (2006) (2)
- Mechanism design for software agents with complete information (2005) (2)
- Validating Agent-Based Models of Large Networked Systems (2019) (2)
- Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms (2021) (2)
- A characterization of nested canalyzing functions with maximum average sensitivity (2018) (2)
- A Unified Approach for Proving Both Easiness and Hardness Results for Succinct Specifications (Preliminary Version) (1995) (2)
- Resource Bounds and Subproblem Independence (2005) (2)
- Refined Single-Threading for Parallel Functional Programming (1995) (1)
- Periodically specified satisfiability problems: An alternative to domino problems (1997) (1)
- Periodically specified satisfiability problems with applications: An alternative to domino problems (1995) (1)
- Computational Aspects of Fault Location and Resilience Problems for Interdependent Infrastructure Networks (2018) (1)
- On the Efficient Approximability of “HARD” Problems: A Survey (2000) (1)
- Complexity of Inferring Local Transition Functions of Discrete Dynamical Systems (2015) (1)
- R63-90 Sequence Generators, Graphs, and Formal Languages (1963) (0)
- I/O automata based verification of finite state distributed systems: complexity issues (1996) (0)
- PERFORMANCE ANALYSIS OF MULTIVERSION ONCURRENCY CONTROL ALGORITHMS 2 (2017) (0)
- On the Complexity of Satisfiability Problems for Algebraic Structures (Preliminary Report) (1988) (0)
- Sequential dynamical systems with threshold functions. (2001) (0)
- Indian Village Sites of the Patuxent River (1965) (0)
- Finding Nontrivial Minimum Fixed Points in Discrete Dynamical Systems: Complexity, Special Case Algorithms and Heuristics (2022) (0)
- Hierarchically and 1-Dimensional Periodically Specified Generalized CNF Satisfiability Problems with Applications (1997) (0)
- The Integrated Subject File. I. Data Base Characteristics (1973) (0)
- Evolution of Similar Configurations in Graph Dynamical Systems (2020) (0)
- A REPLY TO “CALCULUS: A TRIGONOMETRIC PROCEDURE” (1958) (0)
- Deterministic top-down parsing (1971) (0)
- Generalized CNF Satisfiability Problems and Non-Efficient. (1994) (0)
- hurricanes along the U.S. Gulf Coast that resulted in the worst natural disaster in our nation's history (2005) (0)
- Networked Anti-Coordination Games Meet Graphical Dynamical Systems: Equilibria and Convergence (2023) (0)
- An electronic board game (1982) (0)
- Information about the Society (1965) (0)
- The Turing Computational Model (2012) (0)
- Remarks On The 800th Anniversary Of Magna Carta (2015) (0)
- Chapter 10 POLYNOMIAL TIME MECHANISMS FOR COLLECTIVE DECISION MAKING (2003) (0)
- On the application of pair algebra to automata theory (1964) (0)
- Assigning Agents to Increase Network-Based Neighborhood Diversity (2023) (0)
- Three Aboriginal Sites in the Pimlico Area of Baltimore, Maryland (1966) (0)
- Complexity and efficient approximability of two dimensional periodically specified problems (1996) (0)
- Realization Plans for Extensive Form Games without Perfect Recall (2015) (0)
- Approximation algorithms for NEXTtime-hard periodically specified problems and domino problems (1996) (0)
- Behavior-like Strategies for Games without Perfect Recall (2017) (0)
- An Indian Site Survey of the Patuxent River, Maryland (1951) (0)
- Inferring Users ’ Choice Functions in Networked Social Systems Through Active Queries (2018) (0)
- COMPLEXITY&APPROXIMABILITY OF QUANTIFIED&STOCHASTIC CONSTRAINT SATISFACTION PROBLEMS (2001) (0)
- Efficiently Learning the Topology and Behavior of a Networked Dynamical System Via Active Queries (2022) (0)
- Periodically Specified Problems : An Exponential Complexity Gap between Exact and Approximate Solutions (1994) (0)
- Sums-of-Products and Subproblem Independence (2013) (0)
- Using Active Queries to Learn Local Stochastic Behaviors in Social Networks (2018) (0)

This paper list is powered by the following services:

## Other Resources About Richard E. Stearns

## What Schools Are Affiliated With Richard E. Stearns?

Richard E. Stearns is affiliated with the following schools: