BEGIN:VCALENDAR
VERSION:2.0
PRODID:"-//Durham University/Events"
METHOD:PUBLISH
BEGIN:VEVENT
UID:DUEVENT12051
SEQUENCE:0
DTSTAMP:20130523T012202Z
DTSTART:20120308T160000Z
DTEND:20120308T170000Z
STATUS:CONFIRMED
TRANSP:OPAQUE
LOCATION:E245
SUMMARY:Polynomial-Time Algorithms for Multi-type Branching Processes and 
 Stochastic Context-Free Grammars
DESCRIPTION:We show that one can approximate the least fixed point solutio
 n for a multivariate system of monotone probabilistic polynomial equations
  in time polynomial in both the encoding size of the system of equations a
 nd in log(1/delta), where delta>0 is the desired additive error bound of t
 he solution.  (The model of computation is the standard Turing machine mod
 el.)We use this result to resolve several open problems regarding the comp
 utational complexity of computing key quantities associated with some clas
 sic and heavily studied stochastic processes, including multi-type branchi
 ng processes and stochastic context-free grammars. 
END:VEVENT
END:VCALENDAR