# Domain Recursion for Lifted Inference with Existential Quantifiers

arXiv: https://arxiv.org/abs/1707.07763 · HTML: https://mlsanity.com/paper/1707.07763/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jul 2017.

## Built on by (most cited first, 7 of 7)

- [Lifted Algorithms for Symmetric Weighted First-Order Model Sampling](https://mlsanity.com/paper/2308.08828/) (2023)
- [Lifted Inference beyond First-Order Logic](https://mlsanity.com/paper/2308.11738/) (2023)
- [On Exact Sampling in the Two-Variable Fragment of First-Order Logic](https://mlsanity.com/paper/2302.02730/) (2023)
- [Weighted First Order Model Counting with Directed Acyclic Graph Axioms](https://mlsanity.com/paper/2302.09830/) (2023)
- [Polynomial-Time Relational Probabilistic Inference in Open Universes](https://mlsanity.com/paper/2505.04115/) (2025)
- [Model Enumeration of Two-Variable Logic with Quadratic Delay Complexity](https://mlsanity.com/paper/2505.19648/) (2025)
- [A Fast Model Counting Algorithm for Two-Variable Logic with Counting and Modulo Counting Quantifiers](https://mlsanity.com/paper/2605.03391/) (2026)

## Abstract (arXiv)

In recent work, we proved that the domain recursion inference rule makes domain-lifted inference possible on several relational probability models (RPMs) for which the best known time complexity used to be exponential. We also identified two classes of RPMs for which inference becomes domain lifted when using domain recursion. These two classes subsume the largest lifted classes that were previously known. In this paper, we show that domain recursion can also be applied to models with existential quantifiers. Currently, all lifted inference algorithms assume that existential quantifiers have been removed in pre-processing by Skolemization. We show that besides introducing potentially inconvenient negative weights, Skolemization may increase the time complexity of inference. We give two example models where domain recursion can replace Skolemization, avoids the need for dealing with negative numbers, and reduces the time complexity of inference. These two examples may be interesting from three theoretical aspects: 1- they provide a better and deeper understanding of domain recursion and, in general, (lifted) inference, 2- they may serve as evidence that there are larger classes of models for which domain recursion can satisfyingly replace Skolemization, and 3- they may serve as evidence that better Skolemization techniques exist.