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 >>>

We propose a new general primitive called lossy trapdoor
functions (lossy TDFs), and realize it under a variety of different
number theoretic assumptions, including hardness of the decisional
Diffie-Hellman (DDH) problem and the worst-case hardness of
standard lattice problems.

Using lossy TDFs, we develop a new approach for constructing ... more >>>