138 citations · 262 across the 11 of their papers we have counts for
16 papers
Qualitative Multi-Objective Reachability for Ordered Branching MDPs
Kousha Etessami, Emanuel Martinov
We study qualitative multi-objective reachability problems for Ordered Branching Markov Decision Processes (OBMDPs), or equivalently context-free MDPs, building on prior results fo…
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…
Reachability for Branching Concurrent Stochastic Games
Kousha Etessami, Emanuel Martinov, Alistair Stewart +1
We give polynomial time algorithms for deciding almost-sure and limit-sure reachability in Branching Concurrent Stochastic Games (BCSGs). These are a class of infinite-state imperf…
The complexity of approximating a trembling hand perfect equilibrium of a multi-player game in strategic form
Kousha Etessami, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen +1
We consider the task of computing an approximation of a trembling hand perfect equilibrium for an n-player game in strategic form, n >= 3. We show that this task is complete for th…
The complexity of computing a (quasi-)perfect equilibrium for an n-player extensive form game of perfect recall
Kousha Etessami
We study the complexity of computing or approximating refinements of Nash equilibrium for a given finite n-player extensive form game of perfect recall (EFGPR), where n >= 3. Our r…
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…
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…
Approximating the Termination Value of One-Counter MDPs and Stochastic Games
Tomáš Brázdil, Václav Brožek, Kousha Etessami +1
One-counter MDPs (OC-MDPs) and one-counter simple stochastic games (OC-SSGs) are 1-player, and 2-player turn-based zero-sum, stochastic games played on the transition graph of clas…
One-Counter Stochastic Games
Tomáš Brázdil, Václav Brožek, Kousha Etessami
We study the computational complexity of basic decision problems for one-counter simple stochastic games (OC-SSGs), under various objectives. OC-SSGs are 2-player turn-based stocha…
One-Counter Markov Decision Processes
Tomáš Brázdil, Václav Brožek, Kousha Etessami +2
We study the computational complexity of central analysis problems for One-Counter Markov Decision Processes (OC-MDPs), a class of finitely-presented, countable-state MDPs. OC-MDPs…
Multi-Objective Model Checking of Markov Decision Processes
Kousha Etessami, Marta Kwiatkowska, Moshe Y. Vardi +1
We study and provide efficient algorithms for multi-objective model checking problems for Markov Decision Processes (MDPs). Given an MDP, M, and given multiple linear-time (ω-regul…
Recursive Concurrent Stochastic Games
Kousha Etessami, Mihalis Yannakakis
We study Recursive Concurrent Stochastic Games (RCSGs), extending our recent analysis of recursive simple stochastic games to a concurrent setting where the two players choose move…
First-Order and Temporal Logics for Nested Words
Rajeev Alur, Marcelo Arenas, Pablo Barcelo +3
Nested words are a structured model of execution paths in procedural programs, reflecting their call and return nesting structure. Finite nested words also capture the structure of…