BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1438
DTSTAMP:20240626T045748Z
SUMMARY:Counting Problems in Graphical Models
DESCRIPTION:Speaker: Vidya Sagar Sharma (TIFR)\n\nAbstract: \nA graphical m
 odel is a probabilistic model that uses a graph to represent conditional i
 ndependence relations between random variables. We study acyclic directed 
 graphical models\, where a DAG is used to represent conditional independen
 ce relations and causal relationships between random variables. In this mo
 del\, a DAG $D(V = \\{v_1\, v_2\, \\ldots\, v_n\\}\, E)$ represents a prob
 ability distribution $P$\, defined over a set of random variables $V$\, if
  $P(v_1\, v_2\, \\ldots\, v_n) = \\prod_{i}{P(v_i | \\text{Parent}(v_i))}$
 . A node $v_i$ is said to be a parent of $v_j$ in a DAG if $v_i \\rightarr
 ow v_j$ is an edge in $G$. A DAG entails a conditional independence relati
 on $X \\perp Y \\mid Z$ if all the probability distributions represented b
 y the DAG satisfy the conditional independence relation. There can be more
  than one DAG that entails the same set of conditional independence relati
 ons. Such DAGs are said to be Markov equivalent. Markov equivalent DAGs be
 long to the same equivalence class\, called a Markov equivalence class (ME
 C)\, which is graphically represented by the union of the DAGs it contains
 .Many interesting combinatorial problems related to MECs exist in the lite
 rature. One such combinatorial problem is: Given the graphical representat
 ion of an MEC\, find the size of the MEC. The problem arises from the fact
  that a DAG is also used as a causal graph where a directed edge $X \\righ
 tarrow Y$ implies that $X$ is a direct cause of $Y$\, and the size of an M
 EC measures the uncertainty of the causal model when relying solely on obs
 ervational data. In applications\, more information about the underlying D
 AG than that encoded in the MEC may be available\, for example due to acce
 ss to some special set of interventions\, or some domain-specific knowledg
 e. Meek referred to this as \\emph{background knowledge}\, and modeled it 
 as a specification of the directions of some of the edges of the underlyin
 g DAG. Wienöbst et al. show that counting such background knowledge-consi
 stent DAGs of an MEC is \\#P-hard. In this talk\, we discuss an FPT algori
 thm for this problem. Another interesting combinatorial problem is: Given 
 an undirected graph $G$\, count the number of MECs that have the same skel
 eton as $G$. MECs with the same skeleton have statistical significance. In
  this talk\, we discuss an FPT algorithm that counts MECs with the same sk
 eleton. We also discuss an FPT algorithm that counts MECs with better time
  complexity than the previous algorithm when the input graph is chordal. A
 dditionally\, we discuss a polynomial algorithm to solve the problem when 
 the input graph is a tree.\n
URL:https://www.tcs.tifr.res.in/web/events/1438
DTSTART;TZID=Asia/Kolkata:20240628T160000
DTEND;TZID=Asia/Kolkata:20240628T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR