Friday, March 11, 2011

The Arora-Barak-Steurer paper on unique games

I am finally slogging through the Arora-Barak-Steurer paper on a subexponential algorithm for unique games, almost a year after it first came out. I have written a summary of the algorithm and the lemmas that state the structural properties achieved at each step of the algorithm (no proofs). It's not that hard, after all. Teaching it, I think, would require a few lectures:
- one lecture to present the problem, the conjecture, and put it in context (why people care).
- one lecture on expanders (for the preprocessing step)
- one or two lectures on spectral graph methods, proving Cheeger's inequality
- two lectures to present the algorithm and analysis in the Arora-Barak-Steurer paper, including the proof of the variant of Cheeger's inequality.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.