Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Teoria Automatów


On the complexity of conditional independence

Prelegent: Damian Niwiński

2023-06-21 14:15

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.