  Statistical relational models provide compact encodings of probabilistic
dependencies in relational domains, but result in highly intractable graphical
models. The goal of lifted inference is to carry out probabilistic inference
without needing to reason about each individual separately, by instead treating
exchangeable, undistinguished objects as a whole. In this paper, we study the
domain recursion inference rule, which, despite its central role in early
theoretical results on domain-lifted inference, has later been believed
redundant. We show that this rule is more powerful than expected, and in fact
significantly extends the range of models for which lifted inference runs in
time polynomial in the number of individuals in the domain. This includes an
open problem called S4, the symmetric transitivity model, and a first-order
logic encoding of the birthday paradox. We further identify new classes S2FO2
and S2RU of domain-liftable theories, which respectively subsume FO2 and
recursively unary theories, the largest classes of domain-liftable theories
known so far, and show that using domain recursion can achieve exponential
speedup even in theories that cannot fully be lifted with the existing set of
inference rules.
