One-Way Log-Tape Reductions - Juris Hartmanis; Neil Immerman; Stephen R. Mahaney (FOCS, 1978)

Length of Predicate Calculus Formulas as a New Complexity Measure - Neil Immerman (FOCS, 1979)

First Order Expressibility as a New Complexity Measure. - Neil Immerman (1980)

Number of Quantifiers is Better Than Number of Tape Cells. - Neil Immerman (J. Comput. Syst. Sci., 1981)

Relational Queries Computable in Polynomial Time (Extended Abstract) - Neil Immerman (STOC, 1982)

Upper and Lower Bounds for First Order Expressibility. - Neil Immerman (J. Comput. Syst. Sci., 1982)

Languages Which Capture Complexity Classes (Preliminary Report) - Neil Immerman (STOC, 1983)

On Complete Problems for NP$ cap$CoNP. - Juris Hartmanis; Neil Immerman (ICALP, 1985)

Sparse Sets in NP-P: EXPTIME versus NEXPTIME - Juris Hartmanis; Neil Immerman; Vivian Sewelson (Inf. Control., 1985)

Foundations of Knowledge for Distributed Systems. - Michael J. Fischer; Neil Immerman (TARK, 1986)

Relational Queries Computable in Polynomial Time - Neil Immerman (Inf. Control., 1986)

Expressibility as a complexity measure: results and directions. - Neil Immerman (SCT, 1987)

Interpreting Logics of Knowledge in Propositional Dynamic Logic with Converse. - Michael J. Fischer; Neil Immerman (Inf. Process. Lett., 1987)

Languages that Capture Complexity Classes. - Neil Immerman (SIAM J. Comput., 1987)

On uniformity within NC1. - David A. Mix Barrington; Neil Immerman; Howard Straubing (SCT, 1988)

Nondeterministic Space is Closed Under Complementation. - Neil Immerman (SIAM J. Comput., 1988)

Descriptive and Computational Complexity. - Neil Immerman (FCT, 1989)

Expressibility and Parallel Complexity. - Neil Immerman (SIAM J. Comput., 1989)

Relativizing Relativized Computations. - Neil Immerman; Stephen R. Mahaney (Theor. Comput. Sci., 1989)

Definability with Bounded Number of Bound Variables - Neil Immerman; Dexter Kozen (Inf. Comput., 1989)

On Uniformity within NC¹. - David A. Mix Barrington; Neil Immerman; Howard Straubing (J. Comput. Syst. Sci., 1990)

DSPACE[nk] = VAR[k+1]. - Neil Immerman (SCT, 1991)

An optimal lower bound on the number of variables for graph identification. - Jin-yi Cai; Martin Fürer; Neil Immerman (Comb., 1992)

Time, Hardware, and Uniformity. - David A. Mix Barrington; Neil Immerman (SCT, 1994)

McColm's Conjecture - Yuri Gurevich; Neil Immerman; Saharon Shelah (LICS, 1994)

A Syntactic Characterization of NP-Completeness - J. Antonio Medina; Neil Immerman (LICS, 1994)

McColm conjecture. - Yuri Gurevich; Neil Immerman; Saharon Shelah (CoRR, 1994)

Reachability and the Power of Local Ordering. - Kousha Etessami; Neil Immerman (Theor. Comput. Sci., 1995)

The Complexity of Iterated Multiplication - Neil Immerman; Susan Landau 001 (Inf. Comput., 1995)

A Generalization of Fagin's Theorem. - J. Antonio Medina; Neil Immerman (LICS, 1996)

The Expressiveness of a Family of Finite Set Languages. - Neil Immerman; Sushant Patnaik; David W. Stemple (Theor. Comput. Sci., 1996)

Model Checking and Transitive-Closure Logic. - Neil Immerman; Moshe Y. Vardi (CAV, 1997)

Dyn-FO: A Parallel, Dynamic Complexity Class. - Sushant Patnaik; Neil Immerman (J. Comput. Syst. Sci., 1997)

A First-Order Isomorphism Theorem. - Eric Allender; José L. Balcázar; Neil Immerman (SIAM J. Comput., 1997)

Descriptive Complexity and Model Checking. - Neil Immerman (FSTTCS, 1998)

Descriptive complexity. - Neil Immerman (Springer, 1999)

Progress in Descriptive Complexity. - Neil Immerman (Bull. EATCS, 1999)

The Complexity of Decentralized Control of Markov Decision Processes. - Daniel S. Bernstein; Shlomo Zilberstein; Neil Immerman (UAI, 2000)

Tree Canonization and Transitive Closure. - Kousha Etessami; Neil Immerman (Inf. Comput., 2000)

Reachability Logic: An Efficient Fragment of Transitive Closure Logic. - Natasha Alechina; Neil Immerman (Log. J. IGPL, 2000)

Progress in Descriptive Complexity. - Neil Immerman (Current Trends in Theoretical Computer Science, 2001)

An n! Lower Bound on Formula Size. - Micah Adler; Neil Immerman (LICS, 2001)

The Crane Beach Conjecture. - David A. Mix Barrington; Neil Immerman; Clemens Lautemann; Nicole Schweikardt; Denis Thérien (LICS, 2001)

On the unusual effectiveness of logic in computer science. - Joseph Y. Halpern; Robert Harper 001; Neil Immerman; Phokion G. Kolaitis; Moshe Y. Vardi; Victor Vianu (Bull. Symb. Log., 2001)

Number of Variables Is Equivalent to Space. - Neil Immerman; Jonathan F. Buss; David A. Mix Barrington (J. Symb. Log., 2001)

Framework for Analyzing Garbage Collection. - Matthew Hertz; Neil Immerman; J. Eliot B. Moss (IFIP TCS, 2002)

Complete Problems for Dynamic Complexity Classes. - William Hesse; Neil Immerman (LICS, 2002)

Embedding Linkages on an Integer Lattice. - Susan Landau 001; Neil Immerman (Algorithmica, 2002)

The Complexity of Decentralized Control of Markov Decision Processes. - Daniel S. Bernstein; Robert Givan; Neil Immerman; Shlomo Zilberstein (Math. Oper. Res., 2002)

Leader Election Algorithms for Wireless Ad Hoc Networks. - Sudarshan Vasudevan; Brian DeCleene; Neil Immerman; James F. Kurose; Donald F. Towsley (DISCEX (1), 2003)

An n! lower bound on formula size. - Micah Adler; Neil Immerman (ACM Trans. Comput. Log., 2003)

Verification via Structure Simulation. - Neil Immerman; Alexander Moshe Rabinovich; Thomas W. Reps; Shmuel Sagiv; Greta Yorsh (CAV, 2004)

The Boundary Between Decidability and Undecidability for Transitive-Closure Logics. - Neil Immerman; Alexander Moshe Rabinovich; Thomas W. Reps; Shmuel Sagiv; Greta Yorsh (CSL, 2004)

First-order expressibility of languages with neutral letters or: The Crane Beach conjecture. - David A. Mix Barrington; Neil Immerman; Clemens Lautemann; Nicole Schweikardt; Denis Thérien (J. Comput. Syst. Sci., 2005)

Abstraction for Shape Analysis with Fast and Precise Transformers. - Tal Lev-Ami; Neil Immerman; Shmuel Sagiv (CAV, 2006)

Structure Theorem and Strict Alternation Hierarchy for FO2 on Words. - Philipp Weis; Neil Immerman (Circuits, Logic, and Games, 2006)

Constructing Specialized Shape Analyses for Uniform Change. - Tal Lev-Ami; Mooly Sagiv; Neil Immerman; Thomas W. Reps (VMCAI, 2007)

Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words. - Philipp Weis; Neil Immerman (Electron. Colloquium Comput. Complex., 2007)

Learning Generalized Plans Using Abstract Counting. - Siddharth Srivastava 001; Neil Immerman; Shlomo Zilberstein (AAAI, 2008)

On Supporting Kleene Closure over Event Streams. - Daniel Gyllstrom; Jagrati Agrawal; Yanlei Diao; Neil Immerman (ICDE, 2008)

Using Abstraction for Generalized Planning. - Siddharth Srivastava 001; Neil Immerman; Shlomo Zilberstein (ISAIM, 2008)

Efficient pattern matching over event streams. - Jagrati Agrawal; Yanlei Diao; Daniel Gyllstrom; Neil Immerman (SIGMOD Conference, 2008)

First-Order and Temporal Logics for Nested Words. - Rajeev Alur; Marcelo Arenas; Pablo Barceló; Kousha Etessami; Neil Immerman; Leonid Libkin (Log. Methods Comput. Sci., 2008)

Abstract Planning with Unknown Object Quantities and Properties. - Siddharth Srivastava 001; Neil Immerman; Shlomo Zilberstein (SARA, 2009)

Simulating reachability using first-order logic with applications to verification of linked data structures - Tal Lev-Ami; Neil Immerman; Thomas W. Reps; Mooly Sagiv; Siddharth Srivastava 001; Greta Yorsh (Log. Methods Comput. Sci., 2009)

The complexity of satisfiability problems: Refining Schaefer's theorem. - Eric Allender; Michael Bauland; Neil Immerman; Henning Schnoor; Heribert Vollmer (J. Comput. Syst. Sci., 2009)

Computing Applicability Conditions for Plans with Loops. - Siddharth Srivastava 001; Neil Immerman; Shlomo Zilberstein (ICAPS, 2010)

Merging example plans into generalized plans for non-deterministic environments. - Siddharth Srivastava 001; Neil Immerman; Shlomo Zilberstein (AAMAS, 2010)

Finding Reductions Automatically. - Michael S. Crouch; Neil Immerman; J. Eliot B. Moss (Fields of Logic and Computation, 2010)

A simple inductive synthesis methodology and its applications. - Shachar Itzhaky; Sumit Gulwani; Neil Immerman; Mooly Sagiv (OOPSLA, 2010)

What can the GC compute efficiently?: a language for heap assertions at GC time. - Christoph Reichenbach; Neil Immerman; Yannis Smaragdakis; Edward Aftandilian; Samuel Z. Guyer (OOPSLA, 2010)

Recognizing Patterns in Streams with Imprecise Timestamps. - Haopeng Zhang 003; Yanlei Diao; Neil Immerman (Proc. VLDB Endow., 2010)

Termination and Correctness Analysis of Cyclic Control. - Siddharth Srivastava 001; Neil Immerman; Shlomo Zilberstein (AAAI, 2011)

Qualitative Numeric Planning. - Siddharth Srivastava 001; Shlomo Zilberstein; Neil Immerman; Hector Geffner (AAAI, 2011)

Directed Search for Generalized Plans Using Classical Planners. - Siddharth Srivastava 001; Neil Immerman; Shlomo Zilberstein; Tianjiao Zhang (ICAPS, 2011)

A new representation and associated algorithms for generalized planning. - Siddharth Srivastava 001; Neil Immerman; Shlomo Zilberstein (Artif. Intell., 2011)

Experimental Descriptive Complexity. - Marco Carmosino; Neil Immerman; Charles Jordan (Logic and Program Semantics, 2012)

PQL: A Purely-Declarative Java Extension for Parallel Programming. - Christoph Reichenbach; Yannis Smaragdakis; Neil Immerman (ECOOP, 2012)

Applicability conditions for plans with loops: Computability results and algorithms. - Siddharth Srivastava 001; Neil Immerman; Shlomo Zilberstein (Artif. Intell., 2012)

Effectively-Propositional Reasoning about Reachability in Linked Data Structures. - Shachar Itzhaky; Anindya Banerjee 001; Neil Immerman; Aleksandar Nanevski; Mooly Sagiv (CAV, 2013)

Solving Geometry Problems Using a Combination of Symbolic and Numerical Reasoning. - Shachar Itzhaky; Sumit Gulwani; Neil Immerman; Mooly Sagiv (LPAR, 2013)

Auditing a database under retention policies. - Wentian Lu; Gerome Miklau; Neil Immerman (VLDB J., 2013)

Modular reasoning about heap paths via effectively propositional formulas. - Shachar Itzhaky; Anindya Banerjee 001; Neil Immerman; Ori Lahav 001; Aleksandar Nanevski; Mooly Sagiv (POPL, 2014)

On complexity and optimization of expensive queries in complex event processing. - Haopeng Zhang 003; Yanlei Diao; Neil Immerman (SIGMOD Conference, 2014)

Decentralizing SDN Policies. - Oded Padon; Neil Immerman; Aleksandr Karbyshev; Ori Lahav 001; Mooly Sagiv; Sharon Shoham (POPL, 2015)

A Characterization of the Complexity of Resilience and Responsibility for Self-join-free Conjunctive Queries. - Cibele Freire; Wolfgang Gatterbauer; Neil Immerman; Alexandra Meliou (CoRR, 2015)

The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries. - Cibele Freire; Wolfgang Gatterbauer; Neil Immerman; Alexandra Meliou (Proc. VLDB Endow., 2015)

Decidability of inferring inductive invariants. - Oded Padon; Neil Immerman; Sharon Shoham; Aleksandr Karbyshev; Mooly Sagiv (POPL, 2016)

Complexity column. - Neil Immerman (ACM SIGLOG News, 2016)

The k-Dimensional Weisfeiler-Leman Algorithm. - Neil Immerman; Rik Sengupta (CoRR, 2019)

Bounded Quantifier Instantiation for Checking Inductive Invariants. - Yotam M. Y. Feldman; Oded Padon; Neil Immerman; Mooly Sagiv; Sharon Shoham (Log. Methods Comput. Sci., 2019)

First-order quantified separators. - Jason R. Koenig; Oded Padon; Neil Immerman; Alex Aiken (PLDI, 2020)

New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins. - Cibele Freire; Wolfgang Gatterbauer; Neil Immerman; Alexandra Meliou (PODS, 2020)

Complexity and information in invariant inference. - Yotam M. Y. Feldman; Neil Immerman; Mooly Sagiv; Sharon Shoham (Proc. ACM Program. Lang., 2020)

Summing up Smart Transitions. - Neta Elad; Sophie Rain; Neil Immerman; Laura Kovács; Mooly Sagiv (CAV (1), 2021)

A Finer Analysis of Multi-Structural Games and Beyond. - Marco Carmosino; Ronald Fagin; Neil Immerman; Phokion G. Kolaitis; Jonathan Lenchner; Rik Sengupta (CoRR, 2023)

On the Number of Quantifiers Needed to Define Boolean Functions. - Marco Carmosino; Ronald Fagin; Neil Immerman; Phokion G. Kolaitis; Jonathan Lenchner; Rik Sengupta (MFCS, 2024)

What Juris Hartmanis taught me about Reductions. - Neil Immerman (CoRR, 2024)

Parallel Play Saves Quantifiers. - Marco Carmosino; Ronald Fagin; Neil Immerman; Phokion G. Kolaitis; Jonathan Lenchner; Rik Sengupta; R. Ryan Williams (CoRR, 2024)

Multi-Structural Games and Beyond. - Marco Carmosino; Ronald Fagin; Neil Immerman; Phokion G. Kolaitis; Jonathan Lenchner; Rik Sengupta (Log. Methods Comput. Sci., 2024)

Who Wins the Multi-Structural Game? - Ronald Fagin; Neil Immerman; Phokion G. Kolaitis; Jonathan Lenchner; Rik Sengupta (CoRR, 2025)