Speaker:
Ameet Gadekar

Title:
Graph Coloring via Semidefinite Programming

Abstract:

Deciding whether a given graph is 3-colorable is NP-complete. Moreover, coloring a 3-colorable graph using 4 colors is also known to be NP-hard. On the algorithmic side, coloring 3-colorable graphs using as few colors as possible in polynomial time has received extensive attention since 80’s. However, the early results were based on combinatorial techniques and, soon reached their limitations. In the late 90’s, using the algebraic technique of Semidefinite Programming (SDP), Karger, Motwani and Sudan [KMS] in their seminal result, finally broke this barrier. More recent results still rely on the power of Semidefinite Programming. In this talk, we will look at the classical KMS algorithm.

**

Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.

Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.

For the season programme, please see the seminar webpage.