Reproduce “Temporal Properties of Conditional Independence in Dynamic Bayesian Networks” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Rajab Aghamov, Christel Baier, Joel Ouaknine, Jakob Piribauer, Mihir Vahanwala, Isa Vialard
Methods are developed for formally verifying temporal conditional independence (CI) within Dynamic Bayesian Networks (DBNs), distinguishing between structural and stochastic interpretations. The structural CI verification is PSPACE-complete for general DBNs but PTIME for a restricted DBN class, while verifying eventual stochastic CI is shown to be at least as hard as the open Skolem problem.
Key insights
- The evolution of structural conditional independence in DBNs can be precisely characterized, with a general PSPACE-completeness result but PTIME tractability for a restricted class of DBNs.
- DBN-templates can generate structural conditional independence traces with periods exponential in the number of variables, indicating inherent complexity.
- Verifying the 'eventual' holding of stochastic conditional independence is as hard as the Skolem problem for linear recurrence sequences, implying general intractability.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.