Neil Immerman

According to our database, Neil Immerman authored at least 99 papers between 1978 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Parallel Play Saves Quantifiers.

Marco Carmosino, Ronald Fagin, Neil Immerman, Phokion G. Kolaitis, Jonathan Lenchner, Rik Sengupta, R. Ryan Williams

CoRR, 2024

What Juris Hartmanis taught me about Reductions.

Neil Immerman

CoRR, 2024

On the Number of Quantifiers Needed to Define Boolean Functions.

Marco Carmosino, Ronald Fagin, Neil Immerman, Phokion G. Kolaitis, Jonathan Lenchner, Rik Sengupta

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

2023

A Finer Analysis of Multi-Structural Games and Beyond.

Marco Carmosino, Ronald Fagin, Neil Immerman, Phokion G. Kolaitis, Jonathan Lenchner, Rik Sengupta

CoRR, 2023

2021

Summing up Smart Transitions.

Neta Elad, Sophie Rain, Neil Immerman, Laura Kovács, Mooly Sagiv

Proceedings of the Computer Aided Verification - 33rd International Conference, 2021

2020

Complexity and information in invariant inference.

Yotam M. Y. Feldman, Neil Immerman, Mooly Sagiv, Sharon Shoham

Proc. ACM Program. Lang., 2020

New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins.

Cibele Freire, Wolfgang Gatterbauer, Neil Immerman, Alexandra Meliou

Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2020

First-order quantified separators.

Jason R. Koenig, Oded Padon, Neil Immerman, Alex Aiken

Proceedings of the 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation, 2020

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

The k-Dimensional Weisfeiler-Leman Algorithm.

Neil Immerman, Rik Sengupta

CoRR, 2019

2016

Complexity column.

Neil Immerman

ACM SIGLOG News, 2016

Decidability of inferring inductive invariants.

Oded Padon, Neil Immerman, Sharon Shoham, Aleksandr Karbyshev, Mooly Sagiv

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.

Cibele Freire, Wolfgang Gatterbauer, Neil Immerman, Alexandra Meliou

Proc. VLDB Endow., 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

Decentralizing SDN Policies.

Oded Padon, Neil Immerman, Aleksandr Karbyshev, Ori Lahav, Mooly Sagiv, Sharon Shoham

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

2014

On complexity and optimization of expensive queries in complex event processing.

Haopeng Zhang, Yanlei Diao, Neil Immerman

Proceedings of the International Conference on Management of Data, 2014

Modular reasoning about heap paths via effectively propositional formulas.

Shachar Itzhaky, Anindya Banerjee, Neil Immerman, Ori Lahav, Aleksandar Nanevski, Mooly Sagiv

Proceedings of the 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2014

2013

Auditing a database under retention policies.

Wentian Lu, Gerome Miklau, Neil Immerman

VLDB J., 2013

Solving Geometry Problems Using a Combination of Symbolic and Numerical Reasoning.

Shachar Itzhaky, Sumit Gulwani, Neil Immerman, Mooly Sagiv

Proceedings of the Logic for Programming, Artificial Intelligence, and Reasoning, 2013

Effectively-Propositional Reasoning about Reachability in Linked Data Structures.

Shachar Itzhaky, Anindya Banerjee, Neil Immerman, Aleksandar Nanevski, Mooly Sagiv

Proceedings of the Computer Aided Verification - 25th International Conference, 2013

2012

Applicability conditions for plans with loops: Computability results and algorithms.

Siddharth Srivastava, Neil Immerman, Shlomo Zilberstein

Artif. Intell., 2012

PQL: A Purely-Declarative Java Extension for Parallel Programming.

Christoph Reichenbach, Yannis Smaragdakis, Neil Immerman

Proceedings of the ECOOP 2012 - Object-Oriented Programming, 2012

Experimental Descriptive Complexity.

Marco Carmosino, Neil Immerman, Charles Jordan

Proceedings of the Logic and Program Semantics, 2012

2011

A new representation and associated algorithms for generalized planning.

Siddharth Srivastava, Neil Immerman, Shlomo Zilberstein

Artif. Intell., 2011

Directed Search for Generalized Plans Using Classical Planners.

Siddharth Srivastava, Neil Immerman, Shlomo Zilberstein, Tianjiao Zhang

Proceedings of the 21st International Conference on Automated Planning and Scheduling, 2011

Qualitative Numeric Planning.

Siddharth Srivastava, Shlomo Zilberstein, Neil Immerman, Hector Geffner

Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011

Termination and Correctness Analysis of Cyclic Control.

Siddharth Srivastava, Neil Immerman, Shlomo Zilberstein

Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011

2010

Recognizing Patterns in Streams with Imprecise Timestamps.

Haopeng Zhang, Yanlei Diao, Neil Immerman

Proc. VLDB Endow., 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

Proceedings of the 25th Annual ACM SIGPLAN Conference on Object-Oriented Programming, 2010

A simple inductive synthesis methodology and its applications.

Shachar Itzhaky, Sumit Gulwani, Neil Immerman, Mooly Sagiv

Proceedings of the 25th Annual ACM SIGPLAN Conference on Object-Oriented Programming, 2010

Finding Reductions Automatically.

Michael S. Crouch, Neil Immerman, J. Eliot B. Moss

Proceedings of the Fields of Logic and Computation, 2010

Merging example plans into generalized plans for non-deterministic environments.

Siddharth Srivastava, Neil Immerman, Shlomo Zilberstein

Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), 2010

Computing Applicability Conditions for Plans with Loops.

Siddharth Srivastava, Neil Immerman, Shlomo Zilberstein

Proceedings of the 20th International Conference on Automated Planning and Scheduling, 2010

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

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, Greta Yorsh

Log. Methods Comput. Sci., 2009

Abstract Planning with Unknown Object Quantities and Properties.

Siddharth Srivastava, Neil Immerman, Shlomo Zilberstein

Proceedings of the Eighth Symposium on Abstraction, Reformulation, and Approximation, 2009

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

Efficient pattern matching over event streams.

Jagrati Agrawal, Yanlei Diao, Daniel Gyllstrom, Neil Immerman

Proceedings of the ACM SIGMOD International Conference on Management of Data, 2008

Using Abstraction for Generalized Planning.

Siddharth Srivastava, Neil Immerman, Shlomo Zilberstein

Proceedings of the International Symposium on Artificial Intelligence and Mathematics, 2008

On Supporting Kleene Closure over Event Streams.

Daniel Gyllstrom, Jagrati Agrawal, Yanlei Diao, Neil Immerman

Proceedings of the 24th International Conference on Data Engineering, 2008

Learning Generalized Plans Using Abstract Counting.

Siddharth Srivastava, Neil Immerman, Shlomo Zilberstein

Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, 2008

2007

Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words.

Philipp Weis, Neil Immerman

Electron. Colloquium Comput. Complex., 2007

Constructing Specialized Shape Analyses for Uniform Change.

Tal Lev-Ami, Mooly Sagiv, Neil Immerman, Thomas W. Reps

Proceedings of the Verification, 2007

2006

Structure Theorem and Strict Alternation Hierarchy for FO² on Words.

Philipp Weis, Neil Immerman

Proceedings of the Circuits, Logic, and Games, 08.11. - 10.11.2006, 2006

Abstraction for Shape Analysis with Fast and Precise Transformers.

Tal Lev-Ami, Neil Immerman, Shmuel Sagiv

Proceedings of the Computer Aided Verification, 18th International Conference, 2006

2005

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

2004

The Boundary Between Decidability and Undecidability for Transitive-Closure Logics.

Neil Immerman, Alexander Moshe Rabinovich, Thomas W. Reps, Shmuel Sagiv, Greta Yorsh

Proceedings of the Computer Science Logic, 18th International Workshop, 2004

Verification via Structure Simulation.

Neil Immerman, Alexander Moshe Rabinovich, Thomas W. Reps, Shmuel Sagiv, Greta Yorsh

Proceedings of the Computer Aided Verification, 16th International Conference, 2004

2003

An <i>n!</i> lower bound on formula size.

Micah Adler, Neil Immerman

ACM Trans. Comput. Log., 2003

Leader Election Algorithms for Wireless Ad Hoc Networks.

Sudarshan Vasudevan, Brian DeCleene, Neil Immerman, James F. Kurose, Donald F. Towsley

Proceedings of the 3rd DARPA Information Survivability Conference and Exposition (DISCEX-III 2003), 2003

2002

The Complexity of Decentralized Control of Markov Decision Processes.

Daniel S. Bernstein, Robert Givan, Neil Immerman, Shlomo Zilberstein

Math. Oper. Res., 2002

Embedding Linkages on an Integer Lattice.

Susan Landau, Neil Immerman

Algorithmica, 2002

Complete Problems for Dynamic Complexity Classes.

William Hesse, Neil Immerman

Proceedings of the 17th IEEE Symposium on Logic in Computer Science (LICS 2002), 2002

Framework for Analyzing Garbage Collection.

Matthew Hertz, Neil Immerman, J. Eliot B. Moss

Proceedings of the Foundations of Information Technology in the Era of Networking and Mobile Computing, 2002

2001

Number of Variables Is Equivalent to Space.

Neil Immerman, Jonathan F. Buss, David A. Mix Barrington

J. Symb. Log., 2001

On the unusual effectiveness of logic in computer science.

Joseph Y. Halpern, Robert Harper, Neil Immerman, Phokion G. Kolaitis, Moshe Y. Vardi, Victor Vianu

Bull. Symb. Log., 2001

The Crane Beach Conjecture.

David A. Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt, Denis Thérien

Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, 2001

An n! Lower Bound on Formula Size.

Micah Adler, Neil Immerman

Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, 2001

Progress in Descriptive Complexity.

Neil Immerman

Proceedings of the Current Trends in Theoretical Computer Science, 2001

2000

Reachability Logic: An Efficient Fragment of Transitive Closure Logic.

Natasha Alechina, Neil Immerman

Log. J. IGPL, 2000

Tree Canonization and Transitive Closure.

Kousha Etessami, Neil Immerman

Inf. Comput., 2000

The Complexity of Decentralized Control of Markov Decision Processes.

Daniel S. Bernstein, Shlomo Zilberstein, Neil Immerman

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.

Neil Immerman

Bull. EATCS, 1999

Descriptive complexity.

Neil Immerman

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

1998

Descriptive Complexity and Model Checking.

Neil Immerman

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1998

1997

A First-Order Isomorphism Theorem.

Eric Allender, José L. Balcázar, Neil Immerman

SIAM J. Comput., 1997

Dyn-FO: A Parallel, Dynamic Complexity Class.

Sushant Patnaik, Neil Immerman

J. Comput. Syst. Sci., 1997

Model Checking and Transitive-Closure Logic.

Neil Immerman, Moshe Y. Vardi

Proceedings of the Computer Aided Verification, 9th International Conference, 1997

1996

The Expressiveness of a Family of Finite Set Languages.

Neil Immerman, Sushant Patnaik, David W. Stemple

Theor. Comput. Sci., 1996

A Generalization of Fagin's Theorem.

J. Antonio Medina, Neil Immerman

Proceedings of the Proceedings, 1996

1995

The Complexity of Iterated Multiplication

Neil Immerman, Susan Landau

Inf. Comput., January, 1995

Reachability and the Power of Local Ordering.

Kousha Etessami, Neil Immerman

Theor. Comput. Sci., 1995

1994

McColm conjecture.

Yuri Gurevich, Neil Immerman, Saharon Shelah

CoRR, 1994

A Syntactic Characterization of NP-Completeness

J. Antonio Medina, Neil Immerman

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

McColm's Conjecture

Yuri Gurevich, Neil Immerman, Saharon Shelah

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

Time, Hardware, and Uniformity.

David A. Mix Barrington, Neil Immerman

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.

Jin-yi Cai, Martin Fürer, Neil Immerman

Comb., 1992

1991

DSPACE[n^k] = VAR[k+1].

Neil Immerman

Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

1990

On Uniformity within NC¹.

David A. Mix Barrington, Neil Immerman, Howard Straubing

J. Comput. Syst. Sci., 1990

1989

Definability with Bounded Number of Bound Variables

Neil Immerman, Dexter Kozen

Inf. Comput., November, 1989

Relativizing Relativized Computations.

Neil Immerman, Stephen R. Mahaney

Theor. Comput. Sci., 1989

Expressibility and Parallel Complexity.

Neil Immerman

SIAM J. Comput., 1989

Descriptive and Computational Complexity.

Neil Immerman

Proceedings of the Fundamentals of Computation Theory, 1989

1988

Nondeterministic Space is Closed Under Complementation.

Neil Immerman

SIAM J. Comput., 1988

On uniformity within NC¹.

David A. Mix Barrington, Neil Immerman, Howard Straubing

Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987

Languages that Capture Complexity Classes.

Neil Immerman

SIAM J. Comput., 1987

Interpreting Logics of Knowledge in Propositional Dynamic Logic with Converse.

Michael J. Fischer, Neil Immerman

Inf. Process. Lett., 1987

Expressibility as a complexity measure: results and directions.

Neil Immerman

Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987

1986

Relational Queries Computable in Polynomial Time

Neil Immerman

Inf. Control., 1986

Foundations of Knowledge for Distributed Systems.

Michael J. Fischer, Neil Immerman

Proceedings of the 1st Conference on Theoretical Aspects of Reasoning about Knowledge, 1986

1985

Sparse Sets in NP-P: EXPTIME versus NEXPTIME

Juris Hartmanis, Neil Immerman, Vivian Sewelson

Inf. Control., 1985

On Complete Problems for NP$\cap$CoNP.

Juris Hartmanis, Neil Immerman

Proceedings of the Automata, 1985

1983

Languages Which Capture Complexity Classes (Preliminary Report)

Neil Immerman

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

1982

Upper and Lower Bounds for First Order Expressibility.

Neil Immerman

J. Comput. Syst. Sci., 1982

Relational Queries Computable in Polynomial Time (Extended Abstract)

Neil Immerman

Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

1981

Number of Quantifiers is Better Than Number of Tape Cells.

Neil Immerman

J. Comput. Syst. Sci., 1981

1980

First Order Expressibility as a New Complexity Measure.

Neil Immerman

PhD thesis, 1980

1979

Length of Predicate Calculus Formulas as a New Complexity Measure

Neil Immerman

Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978

One-Way Log-Tape Reductions

Juris Hartmanis, Neil Immerman, Stephen R. Mahaney

Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978