[My Computational Complexity Web Log] Howdy from Banff
Another fourth of July out of the states, this time at the Banff International Research Station (BIRS), a Canadian mathematical conference center similar in spirit to Oberwolfach and Dagstuhl. BIRS is hosting a workshop on Advances in Complexity Theory with a pretty impressive collection of researchers.
Today's talks focused on PCPs and their applications. Guy Kindler gave an interesting presentation on his work with Khot, Mossel and O'Donnell showing that under a few believable assumptions, the Goemans-Williamson Max-Cut approximation is optimal.