We prove that computing a Nash equilibrium in a 3-player
game is PPAD-complete, solving a problem left open in our recent result on the complexity of Nash equilibria.

more >>>

We introduce some operators defining new complexity classes from existing ones in the Blum-Shub-Smale theory of computation over the reals. Each one of these operators is defined with the help of a quantifier differing from the usual ones, $\forall$ and $\exists$, and yet having a precise geometric meaning. Our agenda ... more >>>

We prove several new results regarding the relationship between probabilistic time, BPTime(t), and alternating time, \Sigma_{O(1)} Time(t). Our main results are the following:

1) We prove that BPTime(t) \subseteq \Sigma_3 Time(t polylog(t)). Previous results show that BPTime(t) \subseteq \Sigma_2 Time(t^2 log t) (Sipser and Gacs, STOC '83; Lautemann, IPL '83) ... more >>>