tcs math – some mathematics of theoretical computer science

August 26, 2008

Parallel repetition, unique games, and spectral partitioning

Filed under: Math — Tags: , , , — James Lee @ 8:59 am

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

The Shocking Blue Green Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 71 other followers