We resolve the question of the complexity of Nash equilibrium by
showing that the problem of computing a Nash equilibrium in a game
with 4 or more players is complete for the complexity class PPAD.
Our proof uses ideas from the recently-established equivalence
between polynomial-time solvability of normal-form games and
more >>>

We give two applications of Nisan--Wigderson-type ("non-cryptographic") pseudorandom generators in cryptography. Specifically, assuming the existence of an appropriate NW-type generator, we construct:

A one-message witness-indistinguishable proof system for every language in NP, based on any trapdoor permutation. This proof system does not assume a shared random string or any ... more >>>

We investigate the computational hardness of the {\sc Connectivity},
the {\sc Strong Connectivity} and the {\sc Broadcast} type of Range
Assignment Problems in $\R^2$ and $\R^3$.
We present new reductions for the {\sc Connectivity} problem, which
are easily adapted to suit the other two problems. All reductions
are considerably simpler ... more >>>