Kousha Etessami

According to our database, Kousha Etessami authored at least 65 papers between 1995 and 2022.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2022

Finite and Algorithmic Model Theory (Dagstuhl Seminar 22051).

Albert Atserias, Christoph Berkholz, Kousha Etessami, Joanna Ochremiak

Dagstuhl Reports, 2022

2021

The complexity of computing a (quasi-)perfect equilibrium for an <i>n</i>-player extensive form game.

Kousha Etessami

Games Econ. Behav., 2021

Analysis of probabilistic processes and automata theory.

Kousha Etessami

Proceedings of the Handbook of Automata Theory., 2021

2020

Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations.

Kousha Etessami, Alistair Stewart, Mihalis Yannakakis

Math. Oper. Res., 2020

Qualitative Multi-objective Reachability for Ordered Branching MDPs.

Kousha Etessami, Emanuel Martinov

Proceedings of the Reachability Problems - 14th International Conference, 2020

Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria.

Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, Mihalis Yannakakis

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

Recursive stochastic games with positive rewards.

Kousha Etessami, Dominik Wojtczak, Mihalis Yannakakis

Theor. Comput. Sci., 2019

Reachability for Branching Concurrent Stochastic Games.

Kousha Etessami, Emanuel Martinov, Alistair Stewart, Mihalis Yannakakis

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes.

Kousha Etessami, Alistair Stewart, Mihalis Yannakakis

Inf. Comput., 2018

2017

A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes.

Kousha Etessami, Alistair Stewart, Mihalis Yannakakis

SIAM J. Comput., 2017

Algorithms for some infinite-state MDPs and stochastic games.

Kousha Etessami

Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

2015

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

J. ACM, 2015

Recursive Markov Decision Processes and Recursive Stochastic Games.

Kousha Etessami, Mihalis Yannakakis

J. ACM, 2015

2014

The complexity of computing a (perfect) equilibrium for an n-player extensive form game of perfect recall.

Kousha Etessami

CoRR, 2014

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, Troels Bjerre Sørensen

Proceedings of the Algorithmic Game Theory - 7th International Symposium, 2014

2013

Approximating the termination value of one-counter MDPs and stochastic games.

Tomás Brázdil, Václav Brozek, Kousha Etessami, Antonín Kucera

Inf. Comput., 2013

A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing.

Kousha Etessami, Alistair Stewart, Mihalis Yannakakis

Electron. Colloquium Comput. Complex., 2013

The complexity of analyzing infinite-state Markov chains, Markov decision processes, and stochastic games (Invited talk).

Kousha Etessami

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Algorithms for Analyzing and Verifying Infinite-State Recursive Probabilistic Systems.

Kousha Etessami

Proceedings of the Language and Automata Theory and Applications, 2013

Stochastic Context-Free Grammars, Regular Languages, and Newton's Method.

Kousha Etessami, Alistair Stewart, Mihalis Yannakakis

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

Model Checking of Recursive Probabilistic Systems.

Kousha Etessami, Mihalis Yannakakis

ACM Trans. Comput. Log., 2012

Special Section on the Forty-Third Annual ACM Symposium on Theory of Computing (STOC 2011).

Kousha Etessami, Dieter van Melkebeek, Seth Pettie, John Watrous, Salil P. Vadhan

SIAM J. Comput., 2012

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

Kousha Etessami, Alistair Stewart, Mihalis Yannakakis

CoRR, 2012

Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars.

Kousha Etessami, Alistair Stewart, Mihalis Yannakakis

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011

An abort-aware model of transactional programming.

Kousha Etessami, Patrice Godefroid

Int. J. Softw. Tools Technol. Transf., 2011

2010

On the Complexity of Nash Equilibria and Other Fixed Points.

Kousha Etessami, Mihalis Yannakakis

SIAM J. Comput., 2010

Quasi-Birth-Death Processes, Tree-Like QBDs, Probabilistic 1-Counter Automata, and Pushdown Systems.

Kousha Etessami, Dominik Wojtczak, Mihalis Yannakakis

Perform. Evaluation, 2010

One-Counter Markov Decision Processes.

Tomás Brázdil, Václav Brozek, Kousha Etessami, Antonín Kucera, Dominik Wojtczak

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

One-Counter Stochastic Games.

Tomás Brázdil, Václav Brozek, Kousha Etessami

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

2009

Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations.

Kousha Etessami, Mihalis Yannakakis

J. ACM, 2009

2008

Recursive Concurrent Stochastic Games.

Kousha Etessami, Mihalis Yannakakis

Log. Methods Comput. Sci., 2008

Multi-Objective Model Checking of Markov Decision Processes.

Kousha Etessami, Marta Z. Kwiatkowska, Moshe Y. Vardi, Mihalis Yannakakis

Log. Methods Comput. Sci., 2008

First-Order and Temporal Logics for Nested Words.

Rajeev Alur, Marcelo Arenas, Pablo Barceló, Kousha Etessami, Neil Immerman, Leonid Libkin

Log. Methods Comput. Sci., 2008

2007

PReMo : An Analyzer for P robabilistic Re cursive Mo dels.

Dominik Wojtczak, Kousha Etessami

Proceedings of the Tools and Algorithms for the Construction and Analysis of Systems, 2007

On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract).

Kousha Etessami, Mihalis Yannakakis

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2006

Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games.

Kousha Etessami, Mihalis Yannakakis

Proceedings of the STACS 2006, 2006

2005

Analysis of recursive state machines.

Rajeev Alur, Michael Benedikt, Kousha Etessami, Patrice Godefroid, Thomas W. Reps, Mihalis Yannakakis

ACM Trans. Program. Lang. Syst., 2005

Realizability and verification of MSC graphs.

Rajeev Alur, Kousha Etessami, Mihalis Yannakakis

Theor. Comput. Sci., 2005

Fair Simulation Relations, Parity Games, and State Space Reduction for Bu"chi Automata.

Kousha Etessami, Thomas Wilke, Rebecca A. Schuller

SIAM J. Comput., 2005

Algorithmic Verification of Recursive Probabilistic State Machines.

Kousha Etessami, Mihalis Yannakakis

Proceedings of the Tools and Algorithms for the Construction and Analysis of Systems, 2005

On-the-Fly Reachability and Cycle Detection for Recursive State Machines.

Rajeev Alur, Swarat Chaudhuri, Kousha Etessami, P. Madhusudan

Proceedings of the Tools and Algorithms for the Construction and Analysis of Systems, 2005

Checking LTL Properties of Recursive Markov Chains.

Mihalis Yannakakis, Kousha Etessami

Proceedings of the Second International Conference on the Quantitative Evaluaiton of Systems (QEST 2005), 2005

Probability and Recursion.

Kousha Etessami, Mihalis Yannakakis

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

2004

The computational complexity of Evolutionarily Stable Strategies

Kousha Etessami, Andreas Lochbihler

Electron. Colloquium Comput. Complex., 2004

Analysis of Recursive Game Graphs Using Data Flow Equations.

Kousha Etessami

Proceedings of the Verification, 2004

A Temporal Logic of Nested Calls and Returns.

Rajeev Alur, Kousha Etessami, P. Madhusudan

Proceedings of the Tools and Algorithms for the Construction and Analysis of Systems, 2004

Verifying Probabilistic Procedural Programs.

Javier Esparza, Kousha Etessami

Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004

2003

Inference of Message Sequence Charts.

Rajeev Alur, Kousha Etessami, Mihalis Yannakakis

IEEE Trans. Software Eng., 2003

Compression of Partially Ordered Strings.

Rajeev Alur, Swarat Chaudhuri, Kousha Etessami, Sudipto Guha, Mihalis Yannakakis

Proceedings of the CONCUR 2003, 2003

2002

First-Order Logic with Two Variables and Unary Temporal Logic.

Kousha Etessami, Moshe Y. Vardi, Thomas Wilke

Inf. Comput., 2002

A Hierarchy of Polynomial-Time Computable Simulations for Automata.

Kousha Etessami

Proceedings of the CONCUR 2002, 2002

2001

Parametric temporal logic for "model measuring".

Rajeev Alur, Kousha Etessami, Salvatore La Torre, Doron A. Peled

ACM Trans. Comput. Log., 2001

Events and Constraints: A Graphical Editor for Capturing Logic Requirements of Programs.

Margaret H. Smith, Gerard J. Holzmann, Kousha Etessami

Proceedings of the 5th IEEE International Symposium on Requirements Engineering (RE 2001), 2001

Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata.

Kousha Etessami, Thomas Wilke, Rebecca A. Schuller

Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Analysis of Recursive State Machines.

Rajeev Alur, Kousha Etessami, Mihalis Yannakakis

Proceedings of the Computer Aided Verification, 13th International Conference, 2001

2000

A note on a question of Peled and Wilke regarding stutter-invariant LTL.

Kousha Etessami

Inf. Process. Lett., 2000

An Until Hierarchy and Other Applications of an Ehrenfeucht-Fraïssé Game for Temporal Logic.

Kousha Etessami, Thomas Wilke

Inf. Comput., 2000

Tree Canonization and Transitive Closure.

Kousha Etessami, Neil Immerman

Inf. Comput., 2000

From Rule-based to Automata-based Testing.

Kousha Etessami, Mihalis Yannakakis

Proceedings of the Formal Techniques for Distributed System Development, 2000

Optimizing Büchi Automata.

Kousha Etessami, Gerard J. Holzmann

Proceedings of the CONCUR 2000, 2000

1999

Stutter-Invariant Languages, omega-Automata, and Temporal Logic.

Kousha Etessami

Proceedings of the Computer Aided Verification, 11th International Conference, 1999

1998

Dynamic Tree Isomorphism via First-Order Updates.

Kousha Etessami

Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1998

1997

Counting Quantifiers, Successor Relations, and Logarithmic Space.

Kousha Etessami

J. Comput. Syst. Sci., 1997

1996

An Until Hierarchy for Temporal Logic.

Kousha Etessami, Thomas Wilke

Proceedings of the Proceedings, 1996

1995

Reachability and the Power of Local Ordering.

Kousha Etessami, Neil Immerman

Theor. Comput. Sci., 1995