19
$\begingroup$

How would you design a picture to illustrate the unique games conjecture?

This is for a "Current Events" presentation on unique games at the next AMS Joint Meeting and for the booklet that will be produced.

Example of the kind of illustrations produced in the past are at

http://www.ams.org/meetings/lectures/current-events-bulletin

and if you click on the 2006 edition you can see the picture that Madhu Sudan used to illustrate his talk on PCP.

I have thought about using the gadget reducing unique games to max cut, or the Khot-Vishnoi graph for reasonably small size. A good suggestion I received was to draw the label-extended graph of a nearly-satisfiable instance of unique games, and highlight in a different color the vertices corresponding to an optimal solution.

Other suggestions?

Improve this question
$\endgroup$
1
  • $\begingroup$ Dana Moshkovitz had a few slides at the Barriers II rump session. I don't know if they'd have what you need, but you might ask her if you could see them. $\endgroup$
    – Aaron Sterling
    Sep 13, 2010 at 13:11

1 Answer 1

Reset to default
4
$\begingroup$

If I were going to illustrate unique games, I'd do something with a label-extended graph (similar to the suggestion you mentioned).

But specifically, I'd contrast the original constraint graph with the label-extended one. For instance, label edges in the constraint graph with the corresponding equation out of:

$x_1 - x_2 = 0\mod 3$

$x_2 - x_3 = 0\mod 3$

$x_3 - x_1 = 1\mod 3$

Then there will be a (hopefully visually appealing) "twist" between the $x_1$ and $x_3$ vertex clouds in the label-extended graph.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.