Lifting aims at improving the efficiency of probabilistic inference by exploiting symme-tries in the model. Various methods for lifted probabilistic inference have been proposed, but our understanding of these methods and the relationships between them is still lim-ited, compared to their propositional coun-terparts. The only existing theoretical char-acterization of lifting is a completeness re-sult for weighted first-order model counting. This paper addresses the question whether the same completeness result holds for other lifted inference algorithms. We answer this question positively for lifted variable elimina-tion (LVE). Our proof relies on introducing a novel inference operator for LVE. 1

@inproceedings{TaghipourAISTATS13,
  author = "Taghipour, Nima and Fierens, Daan and Van den Broeck, Guy and Davis, Jesse and Blockeel, Hendrik",
  title = "Completeness results for lifted variable elimination",
  booktitle = "Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics (AISTATS), JMLR Workshop and Conference Proceedings",
  location="Scottsdale, USA",
  editor = "Carvalho, Carlos M. and Ravikumar, Pradeep",
  pages = "572–580",
  month = Apr,
  year = "2013",
  url = "http://starai.cs.ucla.edu/papers/TaghipourAISTATS13.pdf",
  keywords   = {conference,selective}
}