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.

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


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