- Cibele Freire, Wolfgang Gatterbauer, Neil Immerman, Alexandra
Meliou, New Results for the Complexity of Resilience for
Binary Conjunctive Queries with Self-Joins, to appear, PODS 2020.
- Yotam Feldman, Neil Immerman, Mooly Sagiv and Sharon Shoham,
"Complexity and Information in Invariant Inference",
to appear 47th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2020).
- Yotam Feldman, Oded Padon, Neil Immerman, Mooly Sagiv and Sharon
Shoham,
"Bounded Quantifier Instantiation for Checking Inductive Invariants",
Logical Methods in Computer Science, August 21, 2019, Volume 15, Issue 3.
A preliminary version appeared in
TACAS 2017.
- Neil Immerman and Rik Sengupta, The
k-Dimensional Weisfeiler-Leman Algorithm, Abstract:
In this note, we provide details of the k-dimensional Weisfeiler-Leman
Algorithm and its analysis from Immerman-Lander (1990). In particular, we
present an optimized version of the algorithm that runs in time O(n
^{k+1}log n), where k is fixed (not varying with n), July, 2019, http://arxiv.org/abs/1907.09582. - Oded Padon, Neil Immerman, Aleksandr Karbyshev, Mooly Sagiv and Sharon
Shoham, "Decidability of Inferring Inductive Invariants", POPL 2016, 217-231.
- Cibele Freire, Wolfgang Gatterbauer, Neil Immerman, Alexandra
Meliou, The Complexity of Resilience and Responsibility for
Self-Join-Free Conjunctive Queries,
*PVLDB,*vol. 9, no. 3 (2015); presented at VLDB 2016; full version: arXiv 1507.00674, "A Characterization of the Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries", July 2, 2015. - Oded Padon, Neil Immerman, Aleksandr Karbyshev, Ori Lahav, Mooly Sagiv, Sharon Shoham,
Decentralizing SDN Policies, POPL 2015.
- Shachar Itzhaky, Anindya Banerjee, Neil Immerman, Ori Lahav, Aleksandar Nanevski, Mooly Sagiv,
Modular Reasoning about Heap Paths via Effectively Propositional Formulas,
*POPL 2014*, 385-396. - Haopeng Zhang, Yanlei Diao, Neil Immerman, On Complexity and
Optimization of Expensive Queries in Complex Event Processing, SIGMOD 2014, 217-228.
- Shachar Itzhaky, Sumit Gulwani, Neil Immerman, Mooly Sagiv,
Solving Geometry Problems Using a Combination of Symbolic and Numerical
Reasoning,
*LPAR-19, Logic for Programming, Artificial Intelligence, and Reasoning*Lecture Notes in Computer Science Volume 8312 (2013), 457-472. - Shachar Itzhaky, Anindya Banerjee, Neil Immerman, Aleks Nanevski and Mooly
Sagiv, Effectively-Propositional Reasoning About Reachability in Linked
Data Structures
*CAV 2013*, 756-772. - Siddharth Srivastava, Neil
Immerman, Shlomo
Zilberstein, Applicability Conditions
for Plans with Loops: Computability Results and Algorithms
*Artificial Intelligence, 191–192*(2012), 1–19. - Wentian Lu, Gerome Miklau, and Neil Immerman, Auditing a Database Under Retention
Policies,
*VLDB Journal*(July, 2012). - Christoph Reichenbach, Yannis Smaragdakis, and Neil
Immerman, PQL: A Purely-Declarative Java Extension for Parallel
Programming, ECOOP 2012.
- Marco Carmosino, Neil Immerman and
Charles
Jordan, Experimental Descriptive
Complexity,
*Logic and Program Semantics: Essays Dedicated to Dexter Kozen on the Occasion of His 60th Birthday*2012, R.L. Constable and A. Silva, eds., Springer LNCS 7230, 24-34. - Siddharth
Srivastava, Neil
Immerman, Shlomo
Zilberstein, A New Representation and Associated Algorithms for
Generalized Planning,
Artificial Intelligence, 175(2), (Feb. 2011), 615-647.
- A Simple Inductive Synthesis Methodology and its
Applications, Shachar Itzhaky, Sumit Gulwani, Neil
Immerman and Mooly Sagiv,
*OOPSLA '10 Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications,*2010 -
What can the GC compute efficiently?: a language for heap assertions at GC timeChristoph Reichenbach, Neil Immerman, Yannis Smaragdakis, Edward E. Aftandilian, Samuel Z. Guyer

OOPSLA '10 Proceedings of the ACM international conference on Object oriented programming systems languages and applications, 2010 - Haopeng Zhang, Yanlei Diao, and Neil Immerman, Recognizing
Patterns in Streams with Imprecise Timestamps, VLDB
2010, 244 - 255.
- Michael Crouch, Neil Immerman, and J. Eliot
B. Moss, Finding Reductions Automatically, in
*Fields of Logic and Computation: Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday*, A. Blass, N. Dershowitz, and W. Reisig, eds., (2010), Springer, 181 - 200. - Siddharth
Srivastava, Neil
Immerman, Shlomo
Zilberstein, Computing Applicability Conditions for Plans with
Loops, ICAPS 2010, 161- 168 (
**Best Paper Award**). - Siddharth
Srivastava, Neil
Immerman, Shlomo
Zilberstein, Merging Example Plans into Generalized Plans for
Non-deterministic Environments,
*Proceedings of the Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS)*(2010), 1341-1348, Toronto, Canada. - Philipp Weis and
Neil Immerman, Structure
theorem and strict alternation hierarchy for FO
^{2}on words, Logical Methods in Computer Science 5(3), paper 4 (2009). A prelimiary version appeared in CSL 2007, 343-357. - Tal Lev-Ami,
Neil Immerman, Tom
Reps, Mooly
Sagiv, Siddharth Srivastava,
and Greta
Yorsh,
Simulating Reachability using First-Order Logic
with Applications to Verification
Of Linked Data
Structures,
Logical
Methods in Computer Science 5(2), paper 12 (2009). A
preliminary version appeared in CADE
'05, 99 - 115. (Abstract.html)
- E. Allender,
Michael Bauland,
Neil Immerman,
Henning
Schnoor,
and Heribert Vollmer,
"The Complexity
of Satisfiability Problems: Refining Schaefer's
Theorem",
*Journal of Computer and System Sciences*75 (2009), 245-254. Preliminary version appeared in MFCS '05, 71-82. (Abstract.html) ( Post's Lattice in Color, diagram by Henning Schnoor) -
Rajeev Alur,
Marcelo Arenas,
Pablo Barceló,
Kousha Etessami,
Neil Immerman, and,
Leonid Libkin,
First-Order and Temporal Logics for Nested Words,
Logical
Methods in Computer Science, 4(4), Paper 11, (2008), 1-44.
Preliminary version appeared in
LICS
2007, 151-160.
- Siddharth
Srivastava, Neil
Immerman, Shlomo
Zilberstein, Learning Generalized Plans
Using Abstract Counting, AAAI 2008, 991-997.
- Jagrati
Agrawal, Yanlei
Diao, Daniel
Gyllstrom, Neil Immerman,
Efficient Pattern Matching Over Event Streams,
SIGMOD '08 Proceedings of the 2008 ACM SIGMOD international conference on Management of data, 2008
- Daniel
Gyllstrom, Jagrati Agrawal, Yanlei
Diao, and Neil
Immerman,
On Supporting Kleene Closure over Event Streams, ICDE 2008, 1391-1393.
- Siddharth
Srivastava,
Neil Immerman, and,
Shlomo
Zilberstein,
Using Abstraction for
Generalized Planning,
*Workshop on Artificial Intelligence Planning and Learning*, in conjunction with*ICAPS-07*; (longer version of this paper). - Tal Lev-Ami,
Mooly
Sagiv, Neil Immerman, and Tom
Reps, Constructing Specialized Shape Analysis for Uniform Change, VMCAI
'07, 215-233.
- Tal Lev-Ami,
Neil Immerman, Mooly
Sagiv,
Abstraction for
Shape Analysis with Fast and Precise Transformers, CAV '06, 533 - 546. (Abstract.html)
- Neil Immerman,
Guest
Column: Progress in Descriptive Complexity,
*SIGACT NEWS*36(4) (2005), p. 24-35. -
D.M. Barrington,
N. Immerman,
Clemens Lautemann,
Nicole Schweikardt, and
Denis Thérien
``First-Order
Expressibility of Languages with Neutral Letters Or: The Crane Beach
Conjecture,''
*JCSS*70(2) (2005), 101-127. A preliminary version appeared in,*LICS '01*, 187-196. (Abstract.html) - Neil Immerman, Alex
Rabinovich, Tom
Reps, Mooly
Sagiv, and Greta
Yorsh,
The Boundary Between Decidability and
Undecidability for Transitive-Closure Logics, CSL '04, 160-174. (Abstract.html)
- Neil Immerman, Computability
and Complexity, in
*Stanford Encyclopedia of Philosophy*. - Neil Immerman, Alex
Rabinovich, Tom
Reps, Mooly
Sagiv, and Greta Yorsh,
Verification
via Structure Simulation, CAV '04, 281-294. (Abstract.html)
- Neil Immerman and Micah Adler An
*n*! lower bound on formula size,*ACM Transactions on Computational Logic (TOCL), 2003*. Preliminary version appeared in*LICS '01*, 197-206. (Abstract.html) -
Bill Hesse and
N. Immerman,
Complete
Problems for Dynamic Complexity Classes,
*LICS '02*, 313-322. (Abstract.html) - Susan Landau and N. Immerman, Embedding Linkages on an Integer
Lattice,
*Algorithmica*, 32(3) (2002), 423--436. (Abstract.html) - D. Bernstein,
R. Givan,
and N. Immerman, and,
S. Zilberstein
"The Complexity of Decentralized Control of Markov Decision Processes".
*Mathematics of Operations Research, 27(4) (2002),*819 - 840. (Abstract.html) - M. Hertz,
and N. Immerman, and,
E. Moss,
``Framework for
Analyzing Garbage Collection,''
*2nd IFIP Theoretical Computer Science Congress*(2002), 230-241. (Abstract.html) - J. Halpern ,
R. Harper ,
N. Immerman,
Ph. Kolaitis,
M. Vardi, and,
V. Vianu,
On the Unusual
Effectiveness of Logic in Computer Science,
*Bulletin of Symbolic Logic.*7(2) (2001), 213-236. - N. Immerman,
J. Buss, and
D.M. Barrington,
Number of Variables Is
Equivalent To Space,
*Journal of Symbolic Logic*, 66(3) (2001), 1217 - 1230. (Abstract.html) - N. Alechina and N. Immerman, Reachability Logic: An
Efficient Fragment of Transitive Closure Logic, Logic Journal of the IGPL 8(3)
(2000), 325-338. (Abstract.html)
- K. Etessami and N. Immerman, Tree Canonization and
Transitive Closure,
*Information and Computation*157(1,2) (2000), 2 - 24. A preliminary version appeared in IEEE Logic In Computer Science Symp. (1995), 331-341. - N. Immerman, Progress in
Descriptive Complexity, guest column on Computational Complexity, EATCS
Bulletin (Feb., 1999). (Abstract.html)
- Descriptive Complexity, N. Immerman, 1999,
Graduate Texts in Computer Science, Springer, New York. Here are Chapters 0, 1 and 2
and Chapter 7 of
*Descriptive Complexity*. -
Descriptive Complexity and Finite Models, edited by N. Immerman and
Ph. Kolaitis,
1997, American Mathematical Society.
- N. Immerman and
M. Vardi, Model Checking and
Transitive Closure Logic, CAV'97, 291 - 302. (Abstract.html)
- S. Patnaik and N. Immerman, Dyn-FO:
A Parallel, Dynamic Complexity Class, JCSS 55(2) (1997), 199-209. A preliminary
version of this paper appeared in PODS (1994):
Dyn-FO (preliminary version): a parallel, dynamic complexity classSushant Patnaik, Neil Immerman

PODS '94 Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, 1994 - D.M. Barrington,
N. Immerman, Time, Hardware, and
Uniformity, in
*Complexity Theory Retrospective II,*L. Hemaspaandra and A. Selman, editors, 1997, Springer-Verlag, 1-22. A preliminary version of this paper appeared in Ninth IEEE Structure in Complexity Theory Symposium (1994), 176- 185. - E. Allender, J. Balcázar and
N. Immerman, A First-Order
Isomorphism Theorem, SIAM J. Computing 26(2) (1997), 557-567. A preliminary
version appeared in Tenth Symp. Theoretical Aspects of Computer Science
(1993), 163-174.
- J.A. Medina and N. Immerman,
*A Generalization of Fagin's Theorem,*IEEE Logic In Computer Science Symp. (1996), 2 -- 12. (Abstract.html) - N. Immerman, S. Patnaik
and D. Stemple, The Expressiveness of a
Family of Finite Set Languages, Theoretical Computer Science, 155(1)
(1996), 111-140. A preliminary version appeared in Tenth ACM Symposium on
Principles of Database Systems (May, 1991), 37-52.
- N. Immerman, Descriptive
Complexity: A Logician's Approach to Computation, Notices of the
American Mathematical Society 42(10) (1995), 1127 - 1133.
- N. Immerman and Susan Landau, The Complexity of
Iterated Multiplication, Information and Computation (116:1) (1995),
103-116.
- K. Etessami and N. Immerman, Reachability and the
Power of Local Ordering,
*Theoretical Computer Science*148(2) (1995), 227-260. A preliminary version of this paper appeared in Eleventh Symp. Theoretical Aspects of Computer Science (1994), 123 - 135. - Y. Gurevich, N. Immerman and S. Shelah,
McColm's
Conjecture, IEEE Logic In Computer Science Symp. (1994), 10-19.
- J.A. Medina and N. Immerman,
*A Syntactic Characterization of NP-Completeness*, IEEE Logic In Computer Science Symp. (1994), 241-250. - Susan Landau and N. Immerman,
*The Similarities (and Differences) between Polynomials and Integers*, International Conference on Number Theoretic and Algebraic Methods in Computer Science (1993), 57-59. - J. Cai,
M. Fürer and N. Immerman, An Optimal Lower Bound
on the Number of Variables for Graph Identification, Combinatorica 12:4
(1992), 389-410. A preliminary version appeared in 30th IEEE FOCS
Symp. (1989), 612-617.
- N. Immerman and E. Lander,
Describing Graphs:
A First-Order Approach to Graph Canonization, in Complexity Theory
Retrospective, Alan Selman, ed., Springer-Verlag (1990), 59-81.
- D.M.
Barrington, N. Immerman and
H. Straubing,
On Uniformity Within
NC
^{1}", JCSS 41:3 (1990), 274 - 306. A preliminary version appeared in Third Annual Structure in Complexity Theory Symp. (1988), 47-59. - N. Immerman, Descriptive
and Computational Complexity, in Computational Complexity Theory, ed.
J. Hartmanis, Lecture Notes for AMS Short Course on ComputationComplexity
Theory, Proc. Symp. in Applied Math. 38, American Mathematical
Society (1989), 75-91.
- N. Immerman and D. Kozen,
Definability
with Bounded Number of Bound Variables,
*Information and Computation*, 83 (1989), 121-139. A preliminary version appeared in IEEE Logic In Computer Science Symp. (1987), 236-244. - N. Immerman, Expressibility
and Parallel Complexity,
*SIAM J. of Comput.*18 (1989), 625-638. - N. Immerman, Nondeterministic
Space is Closed Under
Complementation,
*SIAM J. Comput.*17, No. 5 (Oct., 1988), 935-938. Also appeared in Third Structure in Complexity Theory Symp. (1988), 112-115. - N. Immerman, Languages
That Capture Complexity Classes,
*SIAM J. of Computing*16:4 (1987), 760-778. A preliminary version appeared in 15th ACM STOC Symp. (1983), 347-354. - N. Immerman, Relational
Queries Computable in Polynomial Time,
*Information and Control*68 (1986), 86-104. A preliminary version appeared in 14th ACM STOC Symp. (1982), 147-152:Relational queries computable in polynomial time (Extended Abstract)Neil Immerman

STOC '82 Proceedings of the fourteenth annual ACM symposium on Theory of computing, 1982 -
Sparse sets in NP-P: Exptime versus nexptimeJ. Hartmanis, V. Sewelson, N. Immerman

STOC '83 Proceedings of the fifteenth annual ACM symposium on Theory of computing, 1983 - Neil Immerman, Upper and Lower Bounds for First Order
Expressibility,
*JCSS*25 (1982), 76-98. A preliminary version appeared in*21st IEEE FOCS Symp.*(1980), 74-82. - N. Immerman, "Number
of Quantifiers is Better Than Number of Tape Cells",
*JCSS*22(3) (1981), 384-406. A preliminary version appeared as, ``Length of Predicate Calculus Formulas as a New Complexity Measure,''*20th IEEE FOCS Symp.*(1979), 337-347. I don't have the journal version on line, but here is a tech report version from Cornell, Feb. 1, 1980, that looks pretty close to the journal version. - Neil Immerman, "First-Order
Expressibility as a New Complexity Measure", Ph.D Thesis,
Cornell University, 1980, Cornell Computer Science Dept. Tech Report: 80-432.
- Juris Hartmanis, Neil Immerman and Stephen Mahaney, "One-Way
Log-tape Reductions",
*19th IEEE FOCS Symp.*(1978), 65-72.