---
title: "Polynomial-Time Relational Probabilistic Inference in Open Universes"
authors:
  - "Luise Ge"
  - "Brendan Juba"
  - "Kris Nilsson"
doi: "10.24963/ijcai.2025/1007"
url: "https://ijcai.org/proceedings/2025/1007"
pdf: "https://ijcai.org/proceedings/2025/1007.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "9058-9067"
track: "Main Track"
keywords:
  - "Uncertainty in AI: UAI: Statistical relational AI"
  - "Uncertainty in AI: UAI: Tractable probabilistic models"
---

# Polynomial-Time Relational Probabilistic Inference in Open Universes

Luise Ge, Brendan Juba, Kris Nilsson

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 9058-9067. DOI: [10.24963/ijcai.2025/1007](https://doi.org/10.24963/ijcai.2025/1007)

## Abstract

Reasoning under uncertainty is a fundamental challenge in Artificial Intelligence. As with most of these challenges, there is a harsh dilemma between the expressive power of the language used, and the tractability of the computational problem posed by reasoning. Inspired by human reasoning, we introduce a method of first-order relational probabilistic inference that satisfies both criteria, and can handle hybrid (discrete and continuous) variables. Specifically, we extend sum-of-squares logic of expectation to relational settings, demonstrating that lifted reasoning in the bounded-degree fragment for knowledge bases of bounded quantifier rank can be performed in polynomial time, even with an a priori unknown and/or countably infinite set of objects. Crucially, our notion of tractability is framed in proof-theoretic terms, which extends beyond the syntactic properties of the language or queries.  We are able to derive the tightest bounds provable by proofs of a given degree and size and establish completeness in our sum-of-squares refutations for fixed degrees.