Visualizing Unique Games

Every year, at the AMS Joint Mathematics Meeting, there is a “Current Events” session, with four talks on new and exciting developments in math. Some of the talks are given by speakers who are knowledgeable about the development they are talking about, but unrelated to it.

I think of this as an excellent idea, and in fact I have sometimes fantasized about a theory seminar in which, as a rule, the speakers can only talk about other people’s work. (This has remained a fantasy because it would be too hard to recruit the speakers.) Indeed, at the Berkeley theory lunch, I used to encourage such talks, and I rarely spoke about my own work.

This is all to say that at the 2011 meeting one talk will be about Unique Games (according to my calculations, this means that computer science theory accounts for 1/4 of what’s new and exciting in math, yay!) and I have been invited to deliver it.

In the next three weeks, I am supposed to submit a picture (or a description of it, which will be realized by the AMS graphic designers) that illustrates the topic of my talk.

What picture would you use? I am thinking of a drawing of the Khot-Vishnoi graph or a drawing of the graph used to reduce unique games to Max Cut. A face picture of Subhash would also make sense, but I don’t think it’s what they are looking for. (See here for the graphics accompanying past talks.)


1 thought on “Visualizing Unique Games

  1. How about a drawing of the “label-extended” version of a Unique Games instance? Perhaps with a near-perfect solution (and hence a small non-expanding set) highlighted?

Leave a Reply

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

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

Google photo

You are commenting using your Google 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 )

Connecting to %s