We study the computational complexity of deciding the existence of a
Pure Nash Equilibrium in multi-player strategic games.
We address two fundamental questions: how can we represent a game?, and
how can we represent a game with polynomial pay-off functions?
Our results show that the computational complexity of
deciding ... more >>>

We give a randomized algorithm for testing satisfiability of Boolean formulas in conjunctive normal form with no restriction on clause length. Its running time is at most $2^{n(1-1/\alpha)}$ up to a polynomial factor, where $\alpha = \ln(m/n) + O(\ln \ln m)$ and $n$, $m$ are respectively the number of variables ... more >>>

We give faster approximation algorithms for the
generalization of two NP-hard spanning tree problems. First,
we investigate the problem of minimizing the degree of
minimum spanning forests. The task is to compute for each
number of connected components a minimum spanning forest
whose degree is as small as possible. Fischer
more >>>