Parallel repetition, unique games, and spectral partitioning

Yesterday, Anup Rao pointed me to these two remarkably beautiful papers, which made my morning coffee taste a little better, and the Boston sun feel a bit warmer. I thought I’d pass on the good vibes.

Economical toric spines via Cheeger’s inequality

and

Rounding parallel repetitions of unique games

both of which have their genesis in a recent paper of Ran Raz.

I will actually post detailed notes on these developments in the coming months, as part of my upcoming course on Analytical and geometric methods in the theory of computation (and this link will also work at some point).

[Two more comments worth mentioning:  First, the rounding paper above essentially matches the CMM algorithm even for non-repeated unique games, with a (perhaps) more natural algorithm.  Secondly, as part of RANDOM-APPROX’08, Anup is giving a survey talk on these topics tomorrow morning (Wed, 8/27) at 9am in the Stata center.]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s