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

Kousha Etessami, Alistair Stewart, Mihalis Yannakakis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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/ε), where ε>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.
Original languageEnglish
Title of host publicationProceedings of the 44th symposium on Theory of Computing
Place of PublicationNew York, NY, USA
PublisherACM
Pages579-588
Number of pages10
ISBN (Print)978-1-4503-1245-5
DOIs
Publication statusPublished - 2012

Publication series

NameSTOC '12
PublisherACM

Keywords

  • polynomial time algorithms, probabilistic systems of polynomial equations

Fingerprint Dive into the research topics of 'Polynomial Time Algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars'. Together they form a unique fingerprint.

Cite this