Lune

LICS2021Top-tier venue

A Bunched Logic for Conditional Independence

Jialu Bao, Simon Docherty, Justin Hsu, Alexandra Silva

Abstract

Independence and conditional independence are fundamental concepts for reasoning about groups of random variables in probabilistic programs. Verification methods for independence are still nascent, and existing methods cannot handle conditional independence. We extend the logic of bunched implications (BI) with a non-commutative conjunction and provide a model based on Markov kernels; conditional independence can be directly captured as a logical formula in this model. Noting that Markov kernels are Kleisli arrows for the distribution monad, we then introduce a second model based on the powerset monad and show how it can capture join dependency, a non-probabilistic analogue of conditional independence from database theory. Finally, we develop a program logic for verifying conditional independence in probabilistic programs.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

13 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Asynchronous Probabilistic Couplings in Higher-Order Separation Logic cites A probabilistic separation logic
  • Asynchronous Probabilistic Couplings in Higher-Order Separation Logic cites A separation logic for negative dependence
  • Approximate Relational Reasoning for Higher-Order Probabilistic Programs cites A probabilistic separation logic
  • Approximate Relational Reasoning for Higher-Order Probabilistic Programs cites Asynchronous Probabilistic Couplings in Higher-Order Separation Logic
  • Approximate Relational Reasoning for Higher-Order Probabilistic Programs cites Lilac: A Modal Separation Logic for Conditional Probability
  • Approximate Relational Reasoning for Higher-Order Probabilistic Programs cites A separation logic for negative dependence
  • Lilac: A Modal Separation Logic for Conditional Probability cites A probabilistic separation logic
  • Lilac: A Modal Separation Logic for Conditional Probability cites A separation logic for negative dependence
  • A separation logic for negative dependence cites A probabilistic separation logic
  • Outcome Separation Logic: Local Reasoning for Correctness and Incorrectness with Computational Effects cites A probabilistic separation logic
  • Outcome Separation Logic: Local Reasoning for Correctness and Incorrectness with Computational Effects cites Lilac: A Modal Separation Logic for Conditional Probability
  • Outcome Separation Logic: Local Reasoning for Correctness and Incorrectness with Computational Effects cites A separation logic for negative dependence
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers13

  1. Asynchronous Probabilistic Couplings in Higher-Order Separation LogicSimon Oddershede Gregersen, Alejandro Aguirre, Philipp G. Haselwarter, Joseph Tassarotti et al.POPL 2024 · 23 citations
  2. Lilac: A Modal Separation Logic for Conditional ProbabilityJohn M. Li, Amal Ahmed, Steven HoltzenPLDI 2023 · 22 citations
  3. A separation logic for negative dependenceJialu Bao, Marco Gaboardi, Justin Hsu, Joseph TassarottiPOPL 2022 · 17 citations
  4. Outcome Separation Logic: Local Reasoning for Correctness and Incorrectness with Computational EffectsNoam Zilberstein, Angelina Saliling, Alexandra SilvaOOPSLA 2024 · 16 citations
  5. Approximate Relational Reasoning for Higher-Order Probabilistic ProgramsPhilipp G. Haselwarter, Kwing Hei Li, Alejandro Aguirre, Simon Oddershede Gregersen et al.POPL 2025 · 8 citations

Builds on3

  1. A probabilistic separation logicGilles Barthe, Justin Hsu, Kevin LiaoPOPL 2020 · 35 citations
  2. Semantics of higher-order probabilistic programs with conditioningFredrik Dahlqvist, Dexter KozenPOPL 2020 · 35 citations
  3. Descriptive complexity of real computation and probabilistic independence logicMiika Hannula, Juha Kontinen, Jan Van den Bussche, Jonni VirtemaLICS 2020 · 14 citations

Related papers

  1. Bluebell: An Alliance of Relational Lifting and Independence for Probabilistic ReasoningJialu Bao, Emanuele D'Osualdo, Azadeh FarzanPOPL 2025 · 6 citations
  2. Probabilistic Concurrent Reasoning in Outcome Logic: Independence, Conditioning, and InvariantsNoam Zilberstein, Alexandra Silva, Joseph TassarottiPOPL 2026 · 4 citations
  3. Random Variables, Conditional Independence and Categories of Abstract Sample SpacesDario SteinLICS 2025 · 2 citations
  4. Bayesian Separation Logic: A Logical Foundation and Axiomatic Semantics for Probabilistic ProgrammingShing Hin Ho, Nicolas Wu, Azalea RaadPOPL 2026 · 2 citations
  5. Equivalence and Conditional Independence in Atomic Sheaf LogicAlex SimpsonLICS 2024 · 4 citations
Dusk over the sea between two cliffs drawn in fine vertical lines