138 citations · 262 across the 11 of their papers we have counts for
3 papers · 1 filter
A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
The following two decision problems capture the complexity of comparing integers or rationals that are succinctly represented in product-of-exponentials notation, or equivalently,…
Stochastic Context-Free Grammars, Regular Languages, and Newton's Method
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
We study the problem of computing the probability that a given stochastic context-free grammar (SCFG), G, generates a string in a given regular language L(D) (given by a DFA, D). T…
Upper bounds for Newton's method on monotone polynomial systems, and P-time model checking of probabilistic one-counter automata
Alistair Stewart, Kousha Etessami, Mihalis Yannakakis
A central computational problem for analyzing and model checking various classes of infinite-state recursive probabilistic systems (including quasi-birth-death processes, multi-typ…