Abstract:
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.)
Bio:
Mihalis Yannakakis is the Percy K. and Vida L. W. Hudson Professor of Computer Science
at Columbia University. Prior to joining Columbia, he was Director of the Computing Principles Research Department at Bell Labs and at Avaya Labs, and Professor of Computer Science at Stanford University.
Dr. Yannakakis received his PhD from Princeton University. His research interests include algorithms, complexity, optimization, game theory, databases, testing and verification. He has served on the editorial boards of several journals, including as the past editor-in-chief of the SIAM Journal on Computing, and has chaired various conferences, including the IEEE Symposium on Foundations of Computer Science, the ACM Symposium on Theory of Computing and the ACM Symposium on Principles of Database Systems.
Dr. Yannakakis is a member of the National Academy of Engineering, a recipient of the Knuth Prize, a Fellow of the ACM, and a Bell Labs Fellow.
