We study property testing in the model of bounded degree graphs. It
is well known that in this model many graph properties cannot be
tested with a constant number of queries and it seems reasonable to
conjecture that only few are testable with o(sqrt{n}) queries.
Therefore in this paper ... more >>>

The folk theorem suggests that finding Nash Equilibria
in repeated games should be easier than in one-shot games. In
contrast, we show that the problem of finding any (epsilon) Nash
equilibrium for a three-player infinitely-repeated game is
computationally intractable (even when all payoffs are in
{-1,0,-1}), unless all of PPAD ... more >>>

We present a new approach to constructing pseudorandom generators that fool low-degree polynomials over finite fields, based on the Gowers norm. Using this approach, we obtain the following main constructions of explicitly computable generators $G : \F^s \to \F^n$ that fool polynomials over a prime field $\F$:
\begin{enumerate}
\item a ... more >>>