Coloring 3-colorable graphs
date: November 27th, 2006
speaker: Eddie
Eddie will present his algorithm (joint with Arora and Charikar) that gives
the best known algorithm for coloring a 3-colorable graph (see the ACC paper below).
|
Near optimal algorithms for unique games
date: November 6th and 13th, 2006
speaker: Atri
After focusing on the hardness of MAX-CUT for the last few weeks,
we will now turn our attention to the best known approximation algorithm
for the unique games problem. See the "CMM algorithm" below (under unique games-
we'll see the CMM algorithms for MAX k-CSP and MAX 2-SAT at a later date).
|
Majority is stablest
date: October 30th, 2006
speaker: Nisheeth
Last time we used the Majority is Stablest (MIS) theorem to analyze the KKMO
reduction for MAX-CUT. This time Nisheeth is joining us to present the
proof of MIS. See the MOO paper below.
|
MAX-CUT approximability (continued)
date: October 16th, 2006
speaker: Matt
A continuation of Matt's presentation from last time- Fourier analysis of
boolean functions and the definition of low-degree influence, statement of
Majority is Stablest theorem, and soundness
analysis of the reduction.
If there's time left, we may discuss the proof of Majority is Stablest
and how it ties in geometrically with the GW algorithm.
Papers: See the KKMO and MOO papers below, and also
these
(very nice) lecture notes.
|
MAX-CUT approximability
date: October 9nd, 2006
speaker: Matt
We'll look at the MAXCUT problem, showing the pleasingly geometric upper bound of Goemans and Williamson, and then outline the matching lower bound that follows from the Unique Games conjecture. We'll probably spend most of the time on the lower bound, briefly introducing PCPs before showing how it all leads to Fourier analysis of Boolean functions. We'll then be able to describe the "Majority is Stablest" theorem, and if there's time we'll be able to compare the geometric intuition behind this theorem to that of the Goemans and Williamson upper bound.
Papers: See the GW and KKMO papers below.
|
Unique games intro / MAX-CUT
date: October 2nd, 2006 (+makeup: 10/5/06, 3:30pm, CSE 640)
speaker: James
I'll give an intro to the unique games conjecture and the connection
to SDPs using max-cut as a motivating example. We'll also talk
about what papers we want to read and who wants to present them.
(And finally, I'll attempt to find a student maintainer of this web page.)
For now, here is Lance Fortnow's unique games blog post.
|