Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Lunch 12/03: Joshua Brakensiek

David Wajc wajc at
Thu Dec 3 12:19:16 PST 2020

Reminder: this is starting soon!


On Wed, 2 Dec 2020 at 09:00, David Wajc <wajc at> wrote:

> Hi all,
> Theory lunch will be happening tomorrow at noon (PDT), at our gather
> space:
> (*password:*
>  SongComplexity).
> Josh will tell us about *S**moothed Complexity of 2-player Nash
> Equilibria.*
> *Abstract:*
> We prove that computing a Nash equilibrium of a two-player (n x 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/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.
> Joint work with Shant Boodaghians, Samuel B. Hopkins, and Aviad Rubinstein.
> Cheers,
> David
> PS
> *Pro tip:* To join the zoom talk:
> (1) go to the lecture hall,
> (2) grab a seat, and
> (3)* press X to join the zoom lecture*.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list