CSE logo University of Washington Department of Computer Science & Engineering
 CSE 590z - Theory Seminar, Winter 2006
  CSE Home     590z Previous Quarters  About Us    Search    Contact Info 

    This seminar meets Tuesdays, 1:30pm-2:20pm in EE1 045.
 
To join the e-mail list for the seminar and to find out about other items of interest in theoretical computer science,
students should sign up for the theory-students mailing list.

View the email archive for theory-group for the theory mailing list
 
590z this quarter will focus on a series of recent results characterizing the problem of finding Nash equilibria as complete for the complexity class PPAD, a class of search problems within NP, suggesting that even solving the problem with 2 players is intractible, a result that was surprising to many people working in the field. This will be interspersed with talks by external speakers presenting current research on other topics.
Papers:

Talk Schedule     

Day Speaker(s) Title
Jan 10 Seffi Naor Classification and Partitioning: Recent Bounds
Jan 17 Anna Karlin Nash Equilibria
Jan 25 (3:00-4:00 pm in CSE 503) Liad Blumrosen Implementation with a bounded action space
Jan 27 (12:30-1:20 pm in CSE 403) Mordecai Golin The Quadrangle-Inequality Dynamic-Programming Speedup is a Consequence of Total Monotonicity
Jan 31 Paul Pham PPAD and related complexity classes
Feb 7 Raghavendra Prasad, Ethan Phelps-Goodman Reduction and PPAD-completeness of 3D-Brouwer
Feb 14 Neva Cherniavsky, Matt Cary Overview: Solving 3D-Brouwer using `Converger' circuit
Feb 21 Ioannis Giotis Approximate circuit gates using 2-player Nash equilibria
Feb 28 Mihai Patrascu Cell-Probe Complexity and Predecessor Search



Links:

CSE logo Department of Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX