138 citations · 262 across the 11 of their papers we have counts for
4 papers · 1 filter
Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria
Kousha Etessami, Christos Papadimitriou, Aviad Rubinstein +1
The use of monotonicity and Tarski's theorem in existence proofs of equilibria is very widespread in economics, while Tarski's theorem is also often used for similar purposes in th…
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,…
Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
We show that one can approximate the least fixed point solution for a multivariate system of monotone probabilistic max(min) polynomial equations, referred to as maxPPSs (and minPP…
Polynomial Time Algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
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 siz…