Monday, December 9, 2013
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10627 Berlin
room MA 041
Lecture - 14:15
Abstract:
Structural graph theory has proved to be a powerful tool for coping with computational intractability. It provides a wealth of concepts and results that can be used to design efficient algorithms for hard computational problems such as computing dominating sets etc. on specific classes of graphs that occur naturally in applications. Among the many classes of graphs that have been studied in this context are tree-like graphs, or more formally, classes of graphs of bounded tree-width, planar graphs, graph classes excluding a fixed minor, classes of bounded degree or of bounded local tree-width.
As diverse as these classes of graphs are, they all have in common that they are relatively sparse, i.e. they contain graphs with a moderate number of edges compared to the number of vertices. This naturally raises the question whether "sparsity" may be a key to good algorithmic properties.
Nesetril and Ossona de Mendez proposed a structural property of graph classes called "nowhere dense classes of graphs" as a model to capture "sparsity". Nowhere dense classes of graphs contain all other classes of graphs mentioned above and yet many hard computational problems can be solved efficiently on these classes. Moreover, the algorithms for solving the problems are often much easier than for instance their counterparts on classes of graphs excluding a fixed minor. It turns out that the concept of "nowhere denseness" can equivalently be formalised in many different natural ways. Therefore, nowhere dense classes of graphs seem to capture a natural property of graph classes.
In this talk we give an introduction to nowhere dense classes of graphs. We will present some of the most intuitive definitions of these classes along with algorithmic applications, for instance for computing sparse neighbourhood covers or solving independent and dominating set problems. In particular we will show that every graph property definable in first-order logic can be decided in almost linear time on nowhere dense classes of graphs.
Colloquium - 16:00
Abstract:
Typical questions in the area of conic integral geometry are the following: given a finite number of closed convex cones, each of them (independently) in a uniformly random orientation, what is the probability that they have a nontrivial intersection? Or, given a (standard normal distributed) random semidefinite program, what is the probability that its solution has rank k? These questions have surprisingly simple answers in terms of the intrinsic volumes of the cones. Moreover, the theory of conic intrinsic volumes, though at first glance being close to its well-studied Euclidean counterpart, has remarkable new features and interconnects several different mathematical disciplines, allowing the usage of different tools stemming from areas such as convex and differential geometry, statistics, functional analysis, or combinatorics. One central recent result is the concentration of the conic intrinsic volumes of a cone about its statistical dimension, which in an only slightly oversimplified way may be summarized by saying that
"In high dimensions, a convex cone behaves statistically like a linear subspace."
This result has direct consequences for applications: it gives a rigorous explanation for the ubiquity of phase transition phenomena that appear in high-dimensional applications of convex optimization such as compressed sensing, and also allows the location of these as well as making predictions about quantitative aspects such as the transition widths.
We will survey this fascinating new theory, highlight its various interconnections, and present some intriguing open questions and conjectures, among them a genuine conic analog of the Alexandrov-Fenchel inequalities and a new isoperimetric property of spherical balls.
This is based on joint work with Peter Bürgisser, Martin Lotz, Michael McCoy, Joel Tropp.