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

Kousha Etessami; Alistair Stewart; Mihalis Yannakakis

doi:10.1145/2213977.2214030

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 proceeding › Conference contribution

Abstract / Description of output

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 language	English
Title of host publication	Proceedings of the 44th symposium on Theory of Computing
Place of Publication	New York, NY, USA
Publisher	ACM
Pages	579-588
Number of pages	10
ISBN (Print)	978-1-4503-1245-5
DOIs	https://doi.org/10.1145/2213977.2214030
Publication status	Published - 2012

Publication series

Name	STOC '12
Publisher	ACM

Keywords / Materials (for Non-textual outputs)

polynomial time algorithms, probabilistic systems of polynomial equations

Access to Document

10.1145/2213977.2214030

nI__obSubmitted manuscript, 514 KB

http://doi.acm.org/10.1145/2213977.2214030

Cite this

@inproceedings{982300913b83490986578be1b7ba50a2,

title = "Polynomial Time Algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars",

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.",

keywords = "polynomial time algorithms, probabilistic systems of polynomial equations",

author = "Kousha Etessami and Alistair Stewart and Mihalis Yannakakis",

year = "2012",

doi = "10.1145/2213977.2214030",

language = "English",

isbn = "978-1-4503-1245-5",

series = "STOC '12",

publisher = "ACM",

pages = "579--588",

booktitle = "Proceedings of the 44th symposium on Theory of Computing",

}

TY - GEN

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

AU - Etessami, Kousha

AU - Stewart, Alistair

AU - Yannakakis, Mihalis

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - polynomial time algorithms, probabilistic systems of polynomial equations

U2 - 10.1145/2213977.2214030

DO - 10.1145/2213977.2214030

M3 - Conference contribution

SN - 978-1-4503-1245-5

T3 - STOC '12

SP - 579

EP - 588

BT - Proceedings of the 44th symposium on Theory of Computing

PB - ACM

CY - New York, NY, USA

ER -

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

Abstract / Description of output

Publication series

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Cite this