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

    This seminar meets Tuesdays, 1:30pm-2:20pm in CSE 305.
To join the e-mail list for the seminar and to find out about other items of interest in theoretical computer science:

View the email archive for theory-group for the theory mailing list

590z this quarter will have talks presenting current research.

2009-2010 Academic Year

Talk Schedule     

Day Speaker(s) Title Video
March 30
3:30 PM - 4:30 PM, EEB-105
Vinod Vaikuntanathan, IBM T. J. Watson CSE Colloquium: Side Channels and Clouds: New Challenges in Cryptography Colloquium
April 6
12:30 PM - 2:45 PM
Ofer Dekel, MSR Redmond Special Event: A Tutorial on Modern Learning Theory None
April 13 Parikshit Gopalan, MSR Silicon Valley Matching Vector Codes Quicktime
April 20 Trinh Huynh, University of Washington Hardness Amplification in Proof Complexity Quicktime
April 27 Amos Fiat, Tel Aviv University Combinatorial Auctions with Budgets None
May 4 James Lee, University of Washington Cover times, blanket times, and majorizing measures None
May 11 Glencora Borradaile, Oregon State University A guide to polynomial-time approximation schemes for connectivity problems in planar graphs Quicktime
May 18 Dave Buchfuhrer, Caltech Computation and Incentives in Combinatorial Public Projects
Thursday, May 20,
2:30 PM - 3:30 PM
Ryan O'Donnell, CMU UW Probability Seminar: Kahn-Kalai-Linial and Kruskal-Katona
Monday, May 24,
2:30 PM - 3:30 PM
Claire Mathieu, Brown University UW Probability Seminar: Examples of using randomization in the design of algorithms
May 25 Ori Gurel-Gurevich, MSR Redmond Choice-memory tradeoff in allocations
June 1 Tobias Friedrich, Max Planck Institute for Informatics Quasirandom Load Balancing

Previous Talks - Winter 2009

Day Speaker(s) Title Video
January 12 Anup Rao, University of Washington How to Compress Interactive Communication Quicktime
January 19 Melissa Chase, MSR Redmond Randomizable Proofs and Privacy Applications Quicktime
January 26 David Soloveichik, UW Seelig Lab Computer-Theoretic Abstractions for Molecular Programming Quicktime
February 2 Nati Linial, Hebrew University of Jerusalem Higher-dimensional combinatorics Quicktime
February 9 Zeev Dvir, Institute for Advanced Study On matrix rigidity and locally self-correctable codes Quicktime
February 16 No seminar - Break week
February 23 Nikhil Devanur, MSR Redmond Revisiting bipartite graph matching
March 2 Yael Tauman Kalai, MSR New England Cryptography with Leaky Keys Quicktime
March 9 Mark Braverman, MSR New England Compressing bounded-round communication Quicktime

Previous Talks - Autumn 2009

Day Speaker(s) Title Video
September 29 Scott Aaronson, MIT Quantum Money MP4
October 6 Tim Roughgarden, Stanford Intrinsic Robustness of the Price of Anarchy MP4
Friday, October 9
Christos Papadimitriou, UC Berkeley The Algorithmic Lens: How the Computational Perspective is Transforming the Sciences
October 13
Julia Chuzhoy, TTI Chicago Allocating Goods to Maximize Fairness MP4
October 20 Adam Klivans, UT Austin Distribution-Specific Agnostic Learning MP4
October 27 No seminar - FOCS 2009
November 3 Piotr Indyk, MIT Sparse Recovery Using Sparse Random Matrices MP4
November 10 Satyen Kale, Yahoo! Research Noise Tolerance of Expanders and Sublinear Expander Reconstruction MP4
Thursday, November 12 Niv Buchbinder, MSR New England The Randomized k-Server Conjecture (Online Algorithms meet Linear Programming)
November 17 No seminar - Break week
November 24 Gagan Goel, Georgia Tech Algorithms for Multi-agent Combinatorial Problems with Submodular Cost Functions MP4
December 1 No Seminar - Rescheduled
December 8 Shang-Hua Teng, USC Optimization, Learnability, and Games: From the Lens of Smoothed Analysis Quicktime


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