============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      Computational complexity in probabilistic 
             graphical models
            
Palestrante: Cassio Polpo de Campos
             Dalle Molle Institute for Artificial Intelligence

Hora e Data: 14h, segunda-feira, 04 de junho de 2012

Local:       Sala Multi-usos do Numec

Resumo: 

This talk  presents recent computational  complexity results
for problems in Bayesian  networks, Markov Random fields and
Influence  Diagrams,  such   as  belief  updating,  expected
utility,  most  probable  explanation  (MPE)  and  (partial)
maximum  a posteriori (MAP)  inferences.  The  importance of
these models  has been acknowledged by  the Computer Science
community with the  2011 A. M. Turing award  to Judea Pearl,
who  wrote  a  seminal  book  (among  other  works)  on  the
topic. This presentation focuses on complexity issues: while
belief  updating and  MPE  problems become  easy in  bounded
treewidth networks, expected utility and MAP problems remain
hard  even in networks  with very  simple topology,  such as
binary polytrees  and simple trees. A  Fully Polynomial Time
Approximation   Scheme   for   these  problems   is   shown.
Approximation   schemes   were   recently  thought   to   be
impossible, but  here it is shown otherwise  under some mild
assumptions.