We prove that finding an $\epsilon$-approximate Nash equilibrium is PPAD-complete for constant $\epsilon$ and a particularly simple class of games: polymatrix, degree 3 graphical games, in which each player has only two actions.

As corollaries, we also prove similar inapproximability results for Bayesian Nash equilibrium in a two-player incomplete ... more >>>

We show how to compress communication in distributed protocols in which parties do not have private inputs. More specifically, we present a generic method for converting any protocol in which parties do not have private inputs, into another protocol where each message is "short" while preserving the same number of ... more >>>

We initiate a study of a relaxed version of the standard Erdos-Renyi random graph model, where each edge may depend on a few other edges. We call such graphs dependent random graphs. Our main result in this direction is a thorough understanding of the clique number of dependent random graphs. ... more >>>