  We prove that computing a Nash equilibrium of a two-player ($n \times n$)
game with payoffs in $[-1,1]$ is PPAD-hard (under randomized reductions) even
in the smoothed analysis setting, smoothing with noise of constant magnitude.
This gives a strong negative answer to conjectures of Spielman and Teng [ST06]
and Cheng, Deng, and Teng [CDT09].
  In contrast to prior work proving PPAD-hardness after smoothing by noise of
magnitude $1/\operatorname{poly}(n)$ [CDT09], our smoothed complexity result is
not proved via hardness of approximation for Nash equilibria. This is by
necessity, since Nash equilibria can be approximated to constant error in
quasi-polynomial time [LMM03]. Our results therefore separate smoothed
complexity and hardness of approximation for Nash equilibria in two-player
games.
  The key ingredient in our reduction is the use of a random zero-sum game as a
gadget to produce two-player games which remain hard even after smoothing. Our
analysis crucially shows that all Nash equilibria of random zero-sum games are
far from pure (with high probability), and that this remains true even after
smoothing.
