[Lowerbounds, Upperbounds]

When I was a kid, I was told that a book could gain immortality when people referred to it without even mentioning its title. At that time I wasn’t sure what that meant.

As I grew up, I started to hear about legends of the Green Dragon and the Red Dragon that soar over the great land of Computer Science…

After some twenty years, this semester, the Purple Dragon has finally made its debut to take over the reign of the Red Dragon.

But somehow, deep inside, I felt something looks “wrong” ever since I laid my sight on its cover. I couldn’t identify the subtle cause.

And this morning, ah ha! I finally realized—the computer has disappeared! Indeed, everything else like the Sword of LALR Generator are still there. The computer, however, has disappeared.

I can only imagine that the Knight has an UMPC mounted behind the Shield on his/her forearm. Or perhaps, with the advancement of technology in the last twenty years, the battlefield is now the Matrix.

P.S. Seriously, parsing has definitely advanced in the last twenty years. For a great theory-meets-practice story, you can read about ANTLR. It’s fascinating.

Friday, November 10th, 2006, 3:30 pm
Wean Hall 7220

Eden Chlamtac
Princeton University

Abstract

We describe an algorithm which colors any 3-colorable graph using O(n^0.2074) colors, thus improving the algorithms of Karger, Motwani and Sudan, and Blum and Karger from almost a decade ago. The previous best known algorithm used O(n^{3/14}) colors. We build on these results, which combined semidefinite
programming (SDP) relaxations (specifically, vector chromatic number) with some combinatorial techniques.

We demonstrate a better relation between vector chromatic number and true chromatic number. While this already gives some improvement, we obtain our best result by working with stronger SDP relaxations (e.g. by adding “odd-cycle constraints”). Our analysis uses new geometric ideas inspired by the recent work of Arora, Rao and Vazirani.

This is joint work with Sanjeev Arora and Moses Charikar.