Speakers

Christine Bachoc (University of Bordeaux)

Nikhil Bansal (IBM Research, Yorktown Heights, NY)

Frauke Liers (University of Cologne)

David Steurer (Microsoft Research, New England)

Levent Tuncel (University of Waterloo)

Program

10h00-10h30 Welcome and coffee

10h30-11h15 Christine Bachoc

11h30-12h15 Nikhil Bansal

12h30-14h00 lunch break

14h00-14h45 Frauke Liers

15h00-15h45 David Steurer

16h00-16h45 Levent Tuncel

17h00-18h00 Reception

When and where?

Friday, July 1, 2011

CWI Amsterdam,

Room L120

Where was it?

Additional lectures by young researchers on related topics on Thursday, June 30, 2011

Titles and abstracts

On the theta number of powers of cycle graphs (Christine Bachoc)

In his famous paper introducing the theta number of a graph, L. Lovász gave a closed formula for the theta number of cycle graphs C_k. In this talk we present a closed formula for the powers of cycle graphs C_k^d.

Their complementary graphs, the so-called complete circular graphs K_{k/d} are involved in the recently studied notions of circular clique and chromatic numbers, and of circular perfect graphs. We will show, based on the above mentioned formula, that the circular chromatic number of a circular perfect graph is computable in polynomial time, thus extending a result of Grötschel, Lovász and Schrijver showing that the chromatic number of a perfect graph is poly time.

These results have been obtained in collaboration with Arnaud Pêcher (LABRI, Université Bordeaux I) and Alain Thiery (IMB, Université Bordeaux I).

Finding low discrepancy colorings efficiently (Nikhil Bansal)

The minimum discrepancy problem is the following: Given a collection of sets S_1,...,S_m on some universe, color the elements red and blue such that each set is colored as evenly as possible.

Until recently, most of the results in the area were non-constructive and it was unclear how to find low discrepancy colorings efficiently. In this talk, we will describe an efficient algorithmic approach to find such colorings, based  on a new rounding technique for SDPs. Time permitting, we will also describe how these algorithms can be made deterministic. Interestingly, SDPs will play a key role in the derandomization. 

Parts of the talk are based on joint work with Joel Spencer.

Solving Constrained Cut Problems Exactly (Frauke Liers)

The task of partitioning the set of vertices in a graph into up to k sets such that some objective function is optimized (and maybe some additional constraints are satisfied) has many applications. In computer vision, for example, such tasks appear when automatically recognizing a moving person in two photos that are taken one shortly after the other. In operations research, they show up in facility layout problems. In this talk, we present general and problem-specific exact optimization methods for such NP-hard problems, together with an evaluation on practical instances.

Semidefinite Programming Hierarchies and the Unique Games Conjecture (David Steurer)

Semidefinite programming (SDP) relaxation are a form of convex relaxation that found many uses in algorithms for combinatorial optimization. In the early 1990's several researchers proposed stronger forms of SDP relaxation known as SDP hierarchies. In this talk, I will present a new way of taking algorithmic advantage of these hierarchies to solve constraint satisfaction problems for 2-variable constraints such as Label-Cover, Max-Cut, and Unique-Games.

Specifically, we show an SDP-hierarchy based algorithm that provides arbitrarily good approximation to all these problems in time poly(n)*exp(r), where r is the number of eigenvalues in the constraint graph larger than some constant threshold (depending on the accuracy parameter and type of constraint used).

In particular we get quasipolynomial algorithms for instances whose constraint graph is hypercontractive, as is the case for all the canonical "hard instances" for MAX-CUT and UNIQUE-GAMES. This result gives more reason to consider relatively low levels of an SDP hierarchy as candidate algorithms for refuting Khot's Unique Games Conjecture.

Joint work with Boaz Barak and Prasad Raghavendra.

Some Recent Developments in Lift-and-Project Methods involving Semidefinite Optimization (Levent Tuncel)

First, I will give a quick, high-level view of  popular, SDP-based lift-and-project methods for combinatorial optimization (including those by Lovasz-Schrijver, Sherali-Adams, Lasserre as well as Bienstock-Zuckerberg). Then, I will discuss some of the recent results, some of the fundamental properties of these methods and various techniques used in the analyses of the performance of these methods.

This talk will summarize some of the results in a joint work with Yu-Hin Au and some of the results from a joint work with Bianchi, Escalante and Nasini.

Organizers

Monique Laurent (CWI Amsterdam, Tilburg University), Frank Vallentin (TU Delft, CWI Amsterdam)

List of participants

Alberto Passuello, Anna Gundert, Antonis Varvitsiotis, Bart de Keijzer, Bolor Jargalsaikhan, Christian Schaffner, Christine Bachoc, Cristian Dobre, David Lorch, David Steurer, Dion Gijswijt, Dung Duong, Eddie Kim, Etienne de Klerk, Evan DeCorte, Fernando de Oliveira Filho, Frank Vallentin, Frauke Liers, Frederik von Heymann, Georg Still, Giannicola Scarpa, Giorgos Stathopoulos, Guus Regts, Harry Buhrman, Jop Briet, Julia Sponsel, Kees Roos, Levent Tuncel, Lex Schrijver, Luis Garcias Ramos, Luuk Gijpen, Mariann Nagy, Mirjam Dür, Monique Laurent, Nikhil Bansal, Peter Dickinson, Ronald de Wolf, Ronny Ben-Tal, Shanfei Li, Uwe Truetsch