Liftability of probabilistic inference: Upper and lower bounds

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.(84% acceptance rate)status: publishe