Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Kousha Etessami:

TR13-069 | 1st May 2013
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis

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

The following two decision problems capture the complexity of
comparing integers or rationals that are succinctly represented in
product-of-exponentials notation, or equivalently, via arithmetic
circuits using only multiplication and division gates, and integer

Input instance: four lists of positive integers:

$a_1, \ldots , a_n; \ b_1, \ldots ,b_n; \ ... more >>>

TR04-055 | 27th May 2004
Kousha Etessami, Andreas Lochbihler

The computational complexity of Evolutionarily Stable Strategies

Game theory has been used for a long time to study phenomena in evolutionary biology, beginning systematically with the seminal work of John Maynard Smith. A central concept in this connection has been the notion of an evolutionarily stable strategy (ESS) in a symmetric two-player strategic form game. A regular ... more >>>

ISSN 1433-8092 | Imprint