[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

> THEORY SERIES:
> 
> ~REMINDER~
> 
> The University of Chicago
> THEORY SEMINAR and TTIC
> Tuesday, October 14, 2014
> Ryerson 251 at 3:00 p.m.
> 
> Ruta Mehta
> Georgia Institute of Technology
> www.cc.gatech.edu/~rmehta
>  
> Title: “Resolving The Complexity of Constant Rank Bimatrix Games"
>  
> Abstract: The rank of a bimatrix game (A, B) is defined as the rank of (A+B), e.g., rank-0 are zero-sum games. In 2005, Kannan and Theobald asked if there exists a polynomial time algorithm for constant rank games. We answer this question affirmatively for rank-1 games, and negatively for games with rank three or more (unless PPAD=P); the status of rank-2 games remains unresolved. In the process we obtain a number of other results, including a simpler proof of PPAD-hardness for 2-Nash.
>  
> 
> Joint work with TTIC
> 
> Host: Prof. Alexander Razborov
>  
> *Refreshments will be served in Ryerson 255 at 2:30pm*
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20141014/cd995e87/attachment.htm