BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1349
DTSTAMP:20231025T111829Z
SUMMARY:Counting Markov equivalence classes with the same skeleton
DESCRIPTION:Speaker: Vidya Sagar Sharma (TIFR)\n\nAbstract: \nWe study a di
rected acyclic graphical model\, also known as a Bayesian network. In this
model\, a directed acyclic graph (DAG) is used to represent conditional d
ependence between random variables. Two DAGs are said to be Markov equival
ent if both represent the same set of conditional independence between the
random variables. Verma and Pearl (1990) show that two DAGs are Markov eq
uivalent if\, and only if\, both have the same skeleton (underlying undire
cted graph) and the same v-structures (induced subgraph of the form $a\\ri
ghtarrow b \\leftarrow c$). Markov equivalent DAGs belong to the same Mark
ov equivalent class (MEC). A graphical representation of an MEC is the uni
on of the DAGs it contains.An interesting problem related to the study of
MECs is: for an input undirected graph $G$\, count the MECs with skeleton
$G$. This problem has both graphical and statistical significance. This is
a continuation of last week's talk. In last week's talk\, we discussed a
polynomial time algorithm that solves the problem when the skeleton is a t
ree graph. In this talk\, we will explore a fixed parameter tractable algo
rithm to solve the problem. We will recall the necessary prerequisites fro
m the previous talk.\n
URL:https://www.tcs.tifr.res.in/web/events/1349
DTSTART;TZID=Asia/Kolkata:20231027T170000
DTEND;TZID=Asia/Kolkata:20231027T183000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR