Noga Alon 
Derandomization and Property Testing The probabilistic method is a powerful technique for proving the existence of combinatorial structures or substructures of given ones, with prescribed properties. The method often leads to efficient randomized algorithms for the corresponding algorithmic problems. After a brief discussion of the basic method and its algorithmic aspects, I will discuss various techniques for converting randomized algorithms into deterministic ones. I will also discuss some recent results about property testing, which deals with the design of highly efficient randomized algorithms that test if a given combinatorial structure satisfies a given property or is very far from satisfying it. 

András Frank 
Constructive Characterizations of Connectivity Properties An easy theorem from graph theory asserts that an undirected graph is 2edgeconnected if and only if it may be obtained from a node by applying the following two operations: (i) add a new edge connecting existing nodes, (ii) subdivide an existing edge by a new node. This is a prototype of results the title refers to. In this lecture we overview some wellknown older results such as Tutte's characterization of 3connected graphs, exhibit other not so wellknown characterizations (e.g. Cheriyan and Maheshwari's eardecomposition of 3connected graphs, Mader's theorem on generating all kedgeconnected directed graphs), and derive some recent results of the area (e.g.: an undirected graph contains two edgedisjoint spanning trees after deleting any of its edges if and only if it can be obtained from a node by applying the following to operations: (i) add an edge connecting two existing nodes, (ii) subdivide an existing edge by a new node and connect this node to an existing node). Several examples will be mentioned to demonstrate the usefullness of such characterizations. We will conclude some challenging open questions. 

Michel Goemans 
Multicommodity Flows and Cuts, and Low Distortion Embeddings of Metrics
[tentative] I will describe several results concerning the embedding of certain types of metric spaces into others, either isometrically or with (low) distortion. We will start with classical results, such as the isometric embedding of $l_2$ into $l_1$. We will cover Bourgain's embedding of any metric into $l_1$ or $l_2$ with logarithmic distortion, and also discuss the embedding of negative type metrics. This will lead us to semidefinite programming (and results of Linial et al.), expander graphs, and maximum volume ellipsoids. To motivate the results, we will show the connection between embeddings of metric spaces and multicommodity flows/cuts (or the sparsest cut problem or expansion properties). 

Monique Laurent 
I will present some results that are at the interface between
linear algebra/combinatorial matrix theory and graph theory/
combinatorial optimization. The following "matrix completion problem" will be central to the series of lectures: Given a partial rational matrix, decide if it can be completed to a positive semidefinite matrix and if yes find such a completion. This problem is an instance of semidefinite programming and its complexity is not known. The following topics will be considered. 1. Study classes of graphs (corresponding to the specified entries in the partial matrix) for which the completion problem can be solved in polynomial time. E.g., chordal graphs, graphs with fixed minimum fillin, etc. 2. Find necessary conditions to be satisfied by the specified entries of a completable partial matrix: e.g., conditions based on cut and metric polyhedra, and characterize the graphs for which the conditions are sufficient. 3. Study the cone of psd matrices having a given sparsity pattern and a related graph parameter  the order of a graph. Topics 2 and 3 involve results giving characterizations for some classes of graphs (eg, graphs of order 2, graphs with no induced wheels, ..) with graph theoretic and linear algebraic flavours. 4. Link with other completion problems, e.g., for distance matrices or min/max rank completions. 5. (If time allows) Results about completely positive matrices and doubly nonnegative matrices; in particular, when are the two notions equivalent? 

Alexander Schrijver 
The topic of my course will be polyhedral and polynomialtime
methods in combinatorial optimization.
I will talk on submodular function minimization, bipartite
edgecoloring, and matching forests.
