Neil Immerman

Affiliations:
  • University of Massachusetts Amherst, USA


According to our database1, Neil Immerman authored at least 98 papers between 1978 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2002, "For contributions to complexity theory, descriptive complexity, and database theory.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Parallel Play Saves Quantifiers.
CoRR, 2024

What Juris Hartmanis taught me about Reductions.
CoRR, 2024

2023
A Finer Analysis of Multi-Structural Games and Beyond.
CoRR, 2023

2021
Summing up Smart Transitions.
Proceedings of the Computer Aided Verification - 33rd International Conference, 2021

2020
Complexity and information in invariant inference.
Proc. ACM Program. Lang., 2020

New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins.
Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2020

First-order quantified separators.
Proceedings of the 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation, 2020

2019
Bounded Quantifier Instantiation for Checking Inductive Invariants.
Log. Methods Comput. Sci., 2019

The k-Dimensional Weisfeiler-Leman Algorithm.
CoRR, 2019

2016
Decidability of inferring inductive invariants.
Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2016

2015
The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries.
Proc. VLDB Endow., 2015

A Characterization of the Complexity of Resilience and Responsibility for Self-join-free Conjunctive Queries.
CoRR, 2015

Decentralizing SDN Policies.
Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2015

2014
Complexity column.
ACM SIGLOG News, 2014

On complexity and optimization of expensive queries in complex event processing.
Proceedings of the International Conference on Management of Data, 2014

Modular reasoning about heap paths via effectively propositional formulas.
Proceedings of the 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2014

2013
Auditing a database under retention policies.
VLDB J., 2013

Solving Geometry Problems Using a Combination of Symbolic and Numerical Reasoning.
Proceedings of the Logic for Programming, Artificial Intelligence, and Reasoning, 2013

Effectively-Propositional Reasoning about Reachability in Linked Data Structures.
Proceedings of the Computer Aided Verification - 25th International Conference, 2013

2012
Applicability conditions for plans with loops: Computability results and algorithms.
Artif. Intell., 2012

PQL: A Purely-Declarative Java Extension for Parallel Programming.
Proceedings of the ECOOP 2012 - Object-Oriented Programming, 2012

Experimental Descriptive Complexity.
Proceedings of the Logic and Program Semantics, 2012

2011
A new representation and associated algorithms for generalized planning.
Artif. Intell., 2011

Directed Search for Generalized Plans Using Classical Planners.
Proceedings of the 21st International Conference on Automated Planning and Scheduling, 2011

Qualitative Numeric Planning.
Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011

Termination and Correctness Analysis of Cyclic Control.
Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011

2010
Recognizing Patterns in Streams with Imprecise Timestamps.
Proc. VLDB Endow., 2010

What can the GC compute efficiently?: a language for heap assertions at GC time.
Proceedings of the 25th Annual ACM SIGPLAN Conference on Object-Oriented Programming, 2010

A simple inductive synthesis methodology and its applications.
Proceedings of the 25th Annual ACM SIGPLAN Conference on Object-Oriented Programming, 2010

Finding Reductions Automatically.
Proceedings of the Fields of Logic and Computation, 2010

Merging example plans into generalized plans for non-deterministic environments.
Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), 2010

Computing Applicability Conditions for Plans with Loops.
Proceedings of the 20th International Conference on Automated Planning and Scheduling, 2010

2009
The complexity of satisfiability problems: Refining Schaefer's theorem.
J. Comput. Syst. Sci., 2009

Simulating reachability using first-order logic with applications to verification of linked data structures
Log. Methods Comput. Sci., 2009

Abstract Planning with Unknown Object Quantities and Properties.
Proceedings of the Eighth Symposium on Abstraction, Reformulation, and Approximation, 2009

2008
First-Order and Temporal Logics for Nested Words.
Log. Methods Comput. Sci., 2008

Efficient pattern matching over event streams.
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2008

Using Abstraction for Generalized Planning.
Proceedings of the International Symposium on Artificial Intelligence and Mathematics, 2008

On Supporting Kleene Closure over Event Streams.
Proceedings of the 24th International Conference on Data Engineering, 2008

Learning Generalized Plans Using Abstract Counting.
Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, 2008

2007
Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words.
Electron. Colloquium Comput. Complex., 2007

Constructing Specialized Shape Analyses for Uniform Change.
Proceedings of the Verification, 2007

2006
Structure Theorem and Strict Alternation Hierarchy for FO<sup>2</sup> on Words.
Proceedings of the Circuits, Logic, and Games, 08.11. - 10.11.2006, 2006

Abstraction for Shape Analysis with Fast and Precise Transformers.
Proceedings of the Computer Aided Verification, 18th International Conference, 2006

2005
First-order expressibility of languages with neutral letters or: The Crane Beach conjecture.
J. Comput. Syst. Sci., 2005

2004
The Boundary Between Decidability and Undecidability for Transitive-Closure Logics.
Proceedings of the Computer Science Logic, 18th International Workshop, 2004

Verification via Structure Simulation.
Proceedings of the Computer Aided Verification, 16th International Conference, 2004

2003
An <i>n!</i> lower bound on formula size.
ACM Trans. Comput. Log., 2003

Leader Election Algorithms for Wireless Ad Hoc Networks.
Proceedings of the 3rd DARPA Information Survivability Conference and Exposition (DISCEX-III 2003), 2003

2002
The Complexity of Decentralized Control of Markov Decision Processes.
Math. Oper. Res., 2002

Embedding Linkages on an Integer Lattice.
Algorithmica, 2002

Complete Problems for Dynamic Complexity Classes.
Proceedings of the 17th IEEE Symposium on Logic in Computer Science (LICS 2002), 2002

Framework for Analyzing Garbage Collection.
Proceedings of the Foundations of Information Technology in the Era of Networking and Mobile Computing, 2002

2001
Number of Variables Is Equivalent to Space.
J. Symb. Log., 2001

On the unusual effectiveness of logic in computer science.
Bull. Symb. Log., 2001

The Crane Beach Conjecture.
Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, 2001

An n! Lower Bound on Formula Size.
Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, 2001

Progress in Descriptive Complexity.
Proceedings of the Current Trends in Theoretical Computer Science, 2001

2000
Reachability Logic: An Efficient Fragment of Transitive Closure Logic.
Log. J. IGPL, 2000

Tree Canonization and Transitive Closure.
Inf. Comput., 2000

The Complexity of Decentralized Control of Markov Decision Processes.
Proceedings of the UAI '00: Proceedings of the 16th Conference in Uncertainty in Artificial Intelligence, Stanford University, Stanford, California, USA, June 30, 2000

1999
Progress in Descriptive Complexity.
Bull. EATCS, 1999

Descriptive complexity.
Graduate texts in computer science, Springer, ISBN: 978-0-387-98600-5, 1999

1998
Descriptive Complexity and Model Checking.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1998

1997
A First-Order Isomorphism Theorem.
SIAM J. Comput., 1997

Dyn-FO: A Parallel, Dynamic Complexity Class.
J. Comput. Syst. Sci., 1997

Model Checking and Transitive-Closure Logic.
Proceedings of the Computer Aided Verification, 9th International Conference, 1997

1996
The Expressiveness of a Family of Finite Set Languages.
Theor. Comput. Sci., 1996

A Generalization of Fagin's Theorem.
Proceedings of the Proceedings, 1996

1995
The Complexity of Iterated Multiplication
Inf. Comput., January, 1995

Reachability and the Power of Local Ordering.
Theor. Comput. Sci., 1995

1994
McColm conjecture.
CoRR, 1994

A Syntactic Characterization of NP-Completeness
Proceedings of the Ninth Annual Symposium on Logic in Computer Science (LICS '94), 1994

McColm's Conjecture
Proceedings of the Ninth Annual Symposium on Logic in Computer Science (LICS '94), 1994

Time, Hardware, and Uniformity.
Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1992
An optimal lower bound on the number of variables for graph identification.
Comb., 1992

1991
DSPACE[n<sup>k</sup>] = VAR[k+1].
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

1990
On Uniformity within NC¹.
J. Comput. Syst. Sci., 1990

1989
Definability with Bounded Number of Bound Variables
Inf. Comput., November, 1989

Relativizing Relativized Computations.
Theor. Comput. Sci., 1989

Expressibility and Parallel Complexity.
SIAM J. Comput., 1989

Descriptive and Computational Complexity.
Proceedings of the Fundamentals of Computation Theory, 1989

1988
Nondeterministic Space is Closed Under Complementation.
SIAM J. Comput., 1988

On uniformity within NC<sup>1</sup>.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987
Languages that Capture Complexity Classes.
SIAM J. Comput., 1987

Interpreting Logics of Knowledge in Propositional Dynamic Logic with Converse.
Inf. Process. Lett., 1987

Expressibility as a complexity measure: results and directions.
Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987

1986
Relational Queries Computable in Polynomial Time
Inf. Control., 1986

Foundations of Knowledge for Distributed Systems.
Proceedings of the 1st Conference on Theoretical Aspects of Reasoning about Knowledge, 1986

1985
Sparse Sets in NP-P: EXPTIME versus NEXPTIME
Inf. Control., 1985

On Complete Problems for NP$\cap$CoNP.
Proceedings of the Automata, 1985

1983
Languages Which Capture Complexity Classes (Preliminary Report)
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

1982
Upper and Lower Bounds for First Order Expressibility.
J. Comput. Syst. Sci., 1982

Relational Queries Computable in Polynomial Time (Extended Abstract)
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

1981
Number of Quantifiers is Better Than Number of Tape Cells.
J. Comput. Syst. Sci., 1981

1980
First Order Expressibility as a New Complexity Measure.
PhD thesis, 1980

1979
Length of Predicate Calculus Formulas as a New Complexity Measure
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978
One-Way Log-Tape Reductions
Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978


  Loading...