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.