CSE 590z - Theory Seminar, Winter 2007

University of Washington Department of Computer Science & Engineering

CSE Home

590z Previous Quarters

About Us

Contact Info

This seminar meets Tuesdays, 1:30pm-2:20pm in EEB 037

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.
people from UW that are not students in CSE should sign up for the theory-group mailing list.
people from outside UW should send email to theory-group-request AT cs.

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

590z this quarter will have mix of student presentations and talks by outside speakers presenting current research. The main topic for the student presentations will be some new results about Vertex Cover and Max-Cut problems based on a family of proof systems for 01-programming problems introduced by Lovasz and Schrijver that capture all known semi-definite programming algorithms for these problems. Recent Papers:

Schoenebeck, Trevisan, Tulsiani A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover
Schoenebeck, Trevisan, Tulsiani Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut
Georgiou, Magen, Pitassi, Tourlakis Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy

Talk Schedule

Day Speaker(s) Title

Jan 9 Organizational Meeting Overview

Jan 16 Seffi Naor A Primal Dual Approach to Online Optimization Problems

Jan 23 Amit Chakrabarti Estimating Entropy (and its Friends) on Data Streams

Jan 30 Frank McSherry Mechanism Design via Differential Privacy

Feb 6 Raghavendra Prasad, Anna Gringauze Semidefinite Programming and LS+ part I

Feb 13 Elisa Celis Semidefinite Programming and LS+ part II

Feb 20 Robert Krauthgamer On embedding edit distance into L₁

Feb 27 Mukund Sundararajan Trade-offs in Cost-sharing

Mar 6

Links:


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