Polynomial Time Algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars
Speaker: Mihalis Yannakakis , Columbia University
Date: March 13 2012
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Costis Daskalakis, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
Relevant URL: 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/epsilon), where epsilon > 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.
(Joint work with Kousha Etessami and Alistair Stewart.)
See other events that are part of Theory Colloquium 2011/2012
See other events happening in March 2012
