Previous Conferences & Workshops

May
31
2005

Computer Science/Discrete Mathematics Seminar II

Approximation Algorithms for Unique Games
11:30am|S-101

Khot formulated in 2002 the "Unique Games Conjectures" stating that, for any epsilon > 0, given a system of constraints of a certain form, and the promise that there is an assignment that satisfies a 1-epsilon fraction of constraints, it is...

May
31
2005

Computer Science/Discrete Mathematics Seminar I

A Formal Model for Dynamic Programming
10:30am|S-101

Many algorithms can intuitively be classified into one of a few basic paradigms of algorithms, such as greedy algorithms, dynamic programming, LP rounding, local search, etc. It is natural to ask which problems can be solved using these paradigms...