Kousha Etessami
Edinburgh

Polynomial-Time Algorithms for Multi-type Branching Processes
and Stochastic Context-Free Grammars

We show that one can approximate the least fixed point solution for a
multivariate system of monotone probabilistic polynomial equations in
time polynomial in both the encoding size of the system of equations and
in $\log(1/\delta)$, where $\delta > 0$ is the desired additive error
bound of the solution.  (The model of computation is the standard Turing
machine model.)
  
We use this result to resolve several open problems regarding the
computational complexity of computing key quantities associated with
some classic and heavily studied stochastic processes, including
multi-type branching processes and stochastic context-free grammars.

(This talk describes joint work with Alistair Stewart (U. of Edinburgh)
and Mihalis Yannakakis (Columbia U.), based on a paper that will appear
at STOC 2012.)