You are not logged in |
On the complexity of conditional independence
- Speaker(s)
- Damian Niwiński
- Affiliation
- MIM UW
- Date
- June 21, 2023, 2:15 p.m.
- Room
- room 5050
- Seminar
- Seminar Automata Theory
A conditional independence statement says that, for example, random variables (X,Y) and (W,Y,Z) are independent given a random variable (U,V). Cheuk Ting Li showed in 2022 that it is undecidable if a Boolean combination of such statements is true for all collections of discrete finite-valued random variables. I will present some ideas of the proof that explores symmetry in an ingenious way. If the cardinalities of the random variables in the formula are bounded, the problem is in EXPSPACE, and Michal Makowski showed (in his Master thesis, 2023) that Horn formulas are NEXPTIME-hard. Note that Li's result implies undecidability of the consequence problem for entropic inequalities, but it is still open if we can decide if a given inequality is true.
