Previous Conferences & Workshops

Jun
13
2005

Computer Science/Discrete Mathematics Seminar I

The PCP Theorem by Gap Amplification
11:15am|S-101

Given a set of variables, and a set of local constraints over them (e.g. a 3CNF formula) define the "satisfiability-gap" of the system as the smallest fraction of unsatisfiable constraints. We will describe a new proof for the PCP theorem of [AS...

Jun
01
2005

Computer Science/Discrete Mathematics Seminar III

Computing Equilibria
Christos Papadimitriou
11:15am|S-101

There has been some recent excitement and progress in the long-stalled topic of efficient algorithms for finding equilibria in games and other economic contexts. We discuss some of these developments.

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...