Publications of Neil Immerman

• Marco Carmosino, Ronald Fagin, Neil Immerman, Phokion Kolaitis, Jonathan Lenchner and Rik Sengupta, On the Number of Quantifiers Needed to Define Boolean Functions, to appear in MFCS 2024.

• Neil Immerman, What Juris Hartmanis taught me about Reductions, 2024.

• Marco Carmosino, Ronald Fagin, Neil Immerman, Phokion Kolaitis, Jonathan Lenchner and Rik Sengupta, Multi-Structural Games and Beyond, (2023).

• Neta Elad, Sophie Rain, Neil Immerman, Laura Kovács and Mooly Sagiv, Summing Up Smart Transitions, CAV 2021; full version

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

• Jason R. Koenig, Oded Padon, Neil Immerman and Alex Aiken, First-Order Quantified Separators PLDI 2020.

• Yotam Feldman, Neil Immerman, Mooly Sagiv and Sharon Shoham, Complexity and Information in Invariant Inference, 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+1log 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 time

  Christoph 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² 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)

• Micah Adler and Neil Immerman An n! lower bound on formula size, ACM Transactions on Computational Logic (TOCL), 4(3)  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 class

  Sushant 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¹", 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 as Nondeterministic Space is Closed Under Complementation 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.

• Neil 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:
• Juris Hartmanis, Vivan Sewelson and Neil N. Immerman, "Sparse sets in NP-P: EXPTIME versus NEXPTIME," STOC 1983. Revised version appeared in Information & Control 65 (19850, 158-81.

• 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.

• 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.