It is known that finding a Nash equilibrium for win-lose bimatrix
games, i.e., two-player games where the players' payoffs are zero
and one, is complete for the class PPAD.

We describe a linear time algorithm which computes a Nash
equilibrium for win-lose bimatrix games where the number of winning
positions ... more >>>

The Lov\'asz theta function $\theta(G)$ of a graph $G$ has attracted a lot of attention for its connection with diverse issues, such as communicating without errors and computing large cliques in graphs. Indeed this function enjoys the remarkable property of being computable in polynomial time, despite being sandwitched between clique ... more >>>