Workshop schedule
 9h9h30: Coffee and welcome
 9h3010h15: Etienne de Klerk
Improved lower bounds on crossing numbers of graphs through optimization
Abstract:
The crossing number problem for graphs is to draw (or embed) a graph in the plane with a minimum number of edge crossings. Crossing numbers are of interest for graph visualization, VLSI design, quantum dot cellular automata, RNA folding, and other applications. On the other hand, the problem is notoriously difficult. In 1973, Erdös and Guy wrote that: "Almost all questions that one can ask about crossing numbers remain unsolved." For example, the crossing numbers of complete and complete bipartite graphs are still unknown. The case of the complete bipartite graph is known as Turán's brickyard problem, and was already posed by Paul Turán in the 1940's. Moreover, even for cubic graphs, it is NPhard to compute the crossing number.
Different types of crossing numbers may be defined by restricting drawings; thus the twopage crossing number corresponds to drawings where all vertices are drawn or a circle, and all edges either inside or outside the circle. It is conjectured that the twopage and normal crossing numbers coincide for complete and complete bipartite graphs. In this talk, we will survey some recent results, where improved lower bounds were obtained for (twopage) crossing numbers of complete and complete bipartite graphs through the use of optimization techniques.
(Joint work with D.V. Pasechnik)
Slides

10h1510h45: Coffee break

10h4511h30: Alexandre d'Aspremont
Semidefinite Programming on a Shoestring
Abstract:
We discuss a low rank, very economical, stochastic regularization result for maximum eigenvalue minimization. We then study the complexity of an optimal stochastic minimization algorithm on this problem.
This is joint work with Noureddine El Karoui at U.C. Berkeley.
Slides

11h3012h15: Michel Baes
Minimizing convex functions over integer points
Abstract:
We consider the problem of minimizing a Lipschitzcontinuous and strongly convex functions over integer points in a polytope. We assume that we have at our disposal a blackbox algorithm that solves some special quadratic integer problems with a constant approximation factor. Based on this blackbox procedure, we design and study an iterative procedure to solve our original problem. Despite the generality of the underlying problem, we prove that we can find efficiently, with respect to our assumptions regarding the encoding of the problem, a feasible solution whose objective function value is close to the optimal value. We describe a few situations where we can implement the needed blackbox procedure efficiently.
(Joint work with Alberto Del Pia, Yurii Nesterov, Shmuel Onn, Christian Wagner, and Robert Weismantel)
Slides