We introduce a general framework for defining classes of probabilistic-logic models and associated classes of inference problems. Within this framework we investigate the complexity of inference in terms of the size of logical variable domains, query and evidence, corresponding to different notions of liftability. Surveying existing and introducing new results, we present an initial complexity map for lifted inference. Main results are that lifted inference is infeasible for general quantifier-free first-order probabilistic knowledge bases, but becomes tractable when formulas are restricted to the 2-variable fragment of quantifier-free first-order logic.

@inproceedings{JaegerStarAI12,
  author = "Jaeger, Manfred and Van den Broeck, Guy",
  title = "Liftability of probabilistic inference: {U}pper and lower bounds",
  booktitle = "Proceedings of the 2nd International Workshop on Statistical Relational AI, ",
  year = "2012",
  url="http://starai.cs.ucla.edu/papers/JaegerStarAI12.pdf",
  keywords   = {workshop}
}