Towards Completely Lifted Search-based Probabilistic Inference
  The promise of lifted probabilistic inference is to carry out probabilistic
inference in a relational probabilistic model without needing to reason about
each individual separately (grounding out the representation) by treating the
undistinguished individuals as a block. Current exact methods still need to
ground out in some cases, typically because the representation of the
intermediate results is not closed under the lifted operations. We set out to
answer the question as to whether there is some fundamental reason why lifted
algorithms would need to ground out undifferentiated individuals. We have two
main results: (1) We completely characterize the cases where grounding is
polynomial in a population size, and show how we can do lifted inference in
time polynomial in the logarithm of the population size for these cases. (2)
For the case of no-argument and single-argument parametrized random variables
where the grounding is not polynomial in a population size, we present lifted
inference which is polynomial in the population size whereas grounding is
exponential. Neither of these cases requires reasoning separately about the
individuals that are not explicitly mentioned.
