Neil Immerman
#10,726
Most Influential Person Now
American theoretical computer scientist
Neil Immerman's AcademicInfluence.com Rankings
Neil Immermancomputer-science Degrees
Computer Science
#775
World Rank
#801
Historical Rank
#420
USA Rank
Database
#308
World Rank
#322
Historical Rank
#145
USA Rank
Download Badge
Computer Science
Neil Immerman's Degrees
- PhD Computer Science Cornell University
Similar Degrees You Can Earn
Why Is Neil Immerman Influential?
(Suggest an Edit or Addition)According to Wikipedia, Neil Immerman is an American theoretical computer scientist, a professor of computer science at the University of Massachusetts Amherst. He is one of the key developers of descriptive complexity, an approach he is currently applying to research in model checking, database theory, and computational complexity theory.
Neil Immerman'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 Works
- The Complexity of Decentralized Control of Markov Decision Processes (2000) (1389)
- Nondeterministic space is closed under complementation (1988) (773)
- Descriptive Complexity (1999) (740)
- Relational Queries Computable in Polynomial Time (1986) (727)
- Languages that Capture Complexity Classes (1987) (591)
- An optimal lower bound on the number of variables for graph identification (1989) (541)
- On Uniformity within NC¹ (1990) (427)
- Efficient pattern matching over event streams (2008) (425)
- On uniformity within NC 1 . (1988) (275)
- Describing Graphs: A First-Order Approach to Graph Canonization (1990) (258)
- Upper and lower bounds for first order expressibility (1980) (255)
- Number of Quantifiers is Better Than Number of Tape Cells (1981) (183)
- Definability with Bounded Number of Bound Variables (1989) (156)
- On complexity and optimization of expensive queries in complex event processing (2014) (153)
- Descriptive and Computational Complexity (1989) (148)
- Sparse sets in NP-P: Exptime versus nexptime (1983) (137)
- Expressibility and Parallel Complexity (1989) (136)
- Languages which capture complexity classes (1983) (134)
- Leader election algorithms for wireless ad hoc networks (2003) (125)
- Dyn-FO: A Parallel, Dynamic Complexity Class (1997) (124)
- First-Order and Temporal Logics for Nested Words (2007) (123)
- Recognizing patterns in streams with imprecise timestamps (2010) (117)
- Expressibility as a complexity measure: results and directions (1987) (113)
- On Supporting Kleene Closure over Event Streams (2008) (106)
- On the Unusual Effectiveness of Logic in Computer Science (2001) (103)
- The Boundary Between Decidability and Undecidability for Transitive-Closure Logics (2004) (96)
- Relational queries computable in polynomial time (Extended Abstract) (1982) (95)
- The complexity of satisfiability problems: Refining Schaefer's theorem (2005) (90)
- The complexity of iterated multiplication (1989) (90)
- Simulating Reachability Using First-Order Logic with Applications to Verification of Linked Data Structures (2005) (87)
- A new representation and associated algorithms for generalized planning (2011) (73)
- Foundations of Knowledge for Distributed Systems (1986) (72)
- A simple inductive synthesis methodology and its applications (2010) (67)
- One-way log-tape reductions (1978) (66)
- "An n! lower bound on formula size" (2001) (64)
- A First-Order Isomorphism Theorem (1993) (62)
- A Visual Language for Querying and Updating Graphs (2002) (59)
- Encyclopaedia of Mathematics, Supplement III (2002) (59)
- Learning Generalized Plans Using Abstract Counting (2008) (58)
- SASE + : An Agile Language for Kleene Closure over Event Streams (2007) (57)
- Model Checking and Transitive-Closure Logic (1997) (55)
- Structure Theorem and Strict Alternation Hierarchy for FO2 on Words (2007) (55)
- Effectively-Propositional Reasoning about Reachability in Linked Data Structures (2013) (54)
- The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries (2015) (49)
- The expressiveness of a family of finite set languages (1991) (46)
- Descriptive Complexity and Finite Models (1997) (40)
- Abstraction for Shape Analysis with Fast and Precise Transformers (2006) (38)
- Verification via Structure Simulation (2004) (36)
- Reachability Logic: An Efficient Fragment of Transitive Closure Logic (2000) (34)
- Reachability and the Power of Local Ordering (1995) (32)
- Decentralizing SDN Policies (2015) (32)
- Decidability of inferring inductive invariants (2016) (31)
- Qualitative Numeric Planning (2011) (31)
- Time, hardware, and uniformity (1994) (31)
- Modular reasoning about heap paths via effectively propositional formulas (2014) (30)
- Dynamic computational complexity (2003) (29)
- Directed Search for Generalized Plans Using Classical Planners (2011) (28)
- Tree canonization and transitive closure (1995) (27)
- First-order expressibility of languages with neutral letters or: The Crane Beach conjecture (2005) (26)
- On Complete Problems for NP$\cap$CoNP (1985) (26)
- What can the GC compute efficiently?: a language for heap assertions at GC time (2010) (26)
- Complete problems for dynamic complexity classes (2002) (23)
- First-order quantified separators (2020) (22)
- Dyn-FO (preliminary version): a parallel, dynamic complexity class (1994) (21)
- A Visual Query Language for Relational Knowledge Discovery TITLE2 (2001) (20)
- Power and limits of the Weisfeiler-Leman algorithm (2020) (20)
- Descriptive Complexity: a Logician's Approach to Computation (1995) (19)
- McColm's Conjecture (1994) (18)
- Descriptive Complexity and Model Checking (1998) (18)
- Solving Geometry Problems Using a Combination of Symbolic and Numerical Reasoning (2013) (17)
- Length of predicate calculus formulas as a new complexity measure (1979) (16)
- The Crane Beach Conjecture (2001) (15)
- Computing Applicability Conditions for Plans with Loops (2010) (15)
- Interpreting Logics of Knowledge in Propositional Dynamic Logic with Converse (1987) (15)
- Bounded Quantifier Instantiation for Checking Inductive Invariants (2017) (14)
- On uniformity within NC/sup 1/ (1988) (14)
- Applicability conditions for plans with loops: Computability results and algorithms (2012) (13)
- Relativizing Relativized Computations (1989) (13)
- Finding Reductions Automatically (2010) (13)
- Expressiveness and succinctness of first-order logic on finite words (2011) (13)
- PQL: A Purely-Declarative Java Extension for Parallel Programming (2012) (12)
- A syntactic characterization of NP-completeness (1994) (12)
- Complexity and information in invariant inference (2019) (11)
- Auditing a database under retention policies (2013) (11)
- Merging example plans into generalized plans for non-deterministic environments (2010) (10)
- McColm's conjecture [positive elementary inductions] (1994) (10)
- Number of variables is equivalent to space (2001) (10)
- Framework for Analyzing Garbage Collection (2002) (9)
- Progress in Descriptive Complexity (2001) (8)
- Languages Which Capture Complexity Classes (Preliminary Report) (1983) (7)
- 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), 10-12 July 2007, Wroclaw, Poland, Proceedings (2007) (6)
- WIP: Finding Bugs Automatically in Smart Contracts with Parameterized Invariants (2020) (5)
- The k-Dimensional Weisfeiler-Leman Algorithm (2019) (5)
- New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins (2019) (5)
- The Similarities (and Differances) between Polynomials and Integers (1992) (5)
- Optimizing Expensive Queries in Complex Event Processing (2014) (5)
- Using Abstraction for Generalized Planning (2008) (5)
- A Characterization of the Complexity of Resilience and Responsibility for Conjunctive Queries (2015) (4)
- Abstract Planning with Unknown Object Quantities and Properties (2009) (4)
- Challenges in Finding Generalized Plans (2009) (3)
- Summing Up Smart Transitions (2021) (3)
- Finding Plans with Branches , Loops and Preconditions (2009) (3)
- Constructing Specialized Shape Analyses for Uniform Change (2007) (3)
- First Order Expressibility as a New Complexity Measure (1980) (3)
- The Nature and Power of Fixed-Point Logic with Counting (2015) (2)
- Descriptive complexity and finite models : proceedings of a DIMACS workshop, January 14-17, 1996, Princeton University (1997) (2)
- Constraint Satisfaction Problem and Universal Algebra (2014) (2)
- Decidable logics for expressing heap connectivity (2003) (2)
- Recognizing Patterns in Streams with Imprecise Timestamps Technical Report (2010) (1)
- The Complexity of Satisabilit y Problems: Rening Schaefer's Theorem (2004) (1)
- Dspacen K ] = Vark + 1] (1991) (1)
- Efficient Fragment of Transitive Closure Logic (1999) (1)
- Matiyasevich Yu. V.. Desyataya problema Gil'berta . Russian original of the preceding. Matematicheskaya logika i osnovaniya matematiki. VO “Nauka,” Moscow 1993, 223 pp. Papadimitriou Christos H.. Computational complexity . Addison-Wesley Publishing Company, Reading, Mass., etc., 1994, xv + 523 pp. (1997) (1)
- A generalization of Fagin's theorem (1996) (1)
- McColm conjecture (1994) (1)
- Second-Order Logic and Fagin’s Theorem (1999) (1)
- On the Interplay Between Proof Complexity and SAT Solving (2015) (1)
- JSL volume 62 issue 4 Cover and Back matter and Errata (1997) (0)
- STACS 94, 11th Annual Symposium on Theoretical Aspects of Computer Science, Caen, France, February 24-26, 1994, Proceedings (1994) (0)
- Foundations of Knowledge for Distributed Systems. Revision. (1985) (0)
- Complexity column (2016) (0)
- Complexity column (2016) (0)
- Variants of Courcelle ’ s Theorem for Complexity Classes inside (2016) (0)
- Notices (2002) (0)
- Uniformity and Precomputation (1999) (0)
- Background in Complexity (1999) (0)
- Second-Order Lower Bounds (1999) (0)
- The Role of Ordering (1999) (0)
- Complexity column (2014) (0)
- Self-stabilization by Tree Correction (info) Self-stabilization by Tree Correction (info) Self-stabilization by Tree Correction (1995) (0)
- Computing Applicability Conditions for Plans with Loops : New Results ? (2010) (0)
- Complexity column (2017) (0)
- Auditing a database under retention policies (2012) (0)
- How much time and how much memory space is needed to solve a particular problem ? (1997) (0)
- Embedding Linkages on an Integer Lattice (2002) (0)
- Experimental Descriptive Complexity (2012) (0)
- Termination and Correctness Analysis of Cyclic Control (2011) (0)
- A Finer Analysis of Multi-Structural Games and Beyond (2023) (0)
- Complementation and Transitive Closure (1999) (0)
- Complexity column (2016) (0)
- An Order, Proving Bounds for a Language with Aggre- Gates Hinges on Separation of Tc Lemma 7.1 A) Let M Be a Positive Integer. Then There Exists a Number N > 0 Such That Ntp a 2 M(~ A) = (0)
- Complexity column (2020) (0)
- Complexity column (2018) (0)
- L O ] 1 5 N ov 1 99 4 McColm ’ s Conjecture (2008) (0)
- Weakly Growing Context-sensitive Grammars Chicago Journal of Theoretical Computer Science (1996) (0)
- Pspace-hard Functions Checkable Debate Systems and Approximation Algorithms for Pspace (2007) (0)
- Complexity column (2017) (0)
- Foundations of Software Technology and Theoretical Computer Science (1998) (0)
- Artifact for Article: First-Order Quantified Separators (2020) (0)
- First-Order Reductions (1999) (0)
- Creating generalized procedures by demonstration (2010) (0)
- The Computational Complexity Column Progress in Descriptive Complexity (1998) (0)
- Dynamic Complexity : Recent Updates (2016) (0)
- DeAL: Rich Heap Assertions (Almost) For Free (2010) (0)
- MODEL CHECKING SPARSE STRUCTURES IN DYNAMIC DESCRIPTIVE COMPLEXITY THEORY An undergraduate honors thesis presented by: (2017) (0)
- Background in Logic (1999) (0)
- Association for Symbolic Logic (1996) (0)
- Review: Theodore Baker, John Gill, Robert Solovay, Relativizations of the $\mathscr{P} = ?\mathscr{N} \mathscr{P}$ question; Charles H. Bennett, John Gill, Relative to a Random Oracle $A, P^a \neq NP^A \neq co-NP^A$ with Probability 1 (1986) (0)
- Complexity column (2020) (0)
- Inductive Synthesis (2010) (0)
This paper list is powered by the following services:
Other Resources About Neil Immerman
What Schools Are Affiliated With Neil Immerman?
Neil Immerman is affiliated with the following schools:
