[colloquium] special theory lunch: Christos Papadimitriou on Mon March 6

Sanjeev arora arora at CS.Princeton.EDU
Mon Mar 6 12:08:43 EST 2006

Christos talking at 12:20pm.

Sanjeev Arora wrote:

> Christos Papadimitriou will speak at a special theory lunch on Monday 
> March 6 in the small auditorium in the CS building. I am sending this 
> announcement to the colloquium mailing list too since the talk should 
> be of wider interest.
> Lunch will be served shortly before noon and the talk begins at 12:20. 
> We have to be out of the room by 1:25, and food is not allowed in the 
> auditorium so please come early.
> I apologize for conflicts with other ongoing activities; this time 
> meshed best with the speaker's schedule.
> His abstract appears below.
> Sanjeev
> ---------------
> Christos H. Papadimitriou
> UC, Berkeley
> In 1951 Nash showed that every game has a mixed
>       equilibrium; whether such an equilibrium can be found
>       efficiently has been open since that time. Two decades later
>       Aumann proposed a relaxation called correlated equilibrium,
>       which can be found efficiently by linear programming. These
>       two problems become more interesting and meaningful in the
>       case of succinctly representable multiplayer games. For
>       correlated equilibria, a novel use of the ellipsoid algorithm
>       yields a polynomial-time algorithm in this case; for Nash
>       equilibria a sequence of reductions (discovered in
>       collaboration with Costas Daskalakis and Paul Goldberg) sheds
>       light to the complexity of finding Nash equilibria.
> _______________________________________________
> colloquium mailing list
> colloquium at lists.cs.princeton.edu
> https://lists.cs.princeton.edu/mailman/listinfo/colloquium


I am recovering from RSI and often compose email using handwriting recognition or voice recognition software. My apologies for
minor errors.

Sanjeev Arora
Computer Science Department
Princeton University

More information about the colloquium mailing list