Andreas Holmsen, Topological methods in matching theory

March 1st, 2015
Topological methods in matching theory
Andreas Holmsen
Department of Mathematical Sciences, KAIST
2015/4/7 Tue 4PM-5PM
Around 15 years ago, Aharoni and Haxell gave a wonderful generalization of Hall’s marriage theorem. Their proof introduced topological methods in matching theory which were further developed by Berger, Meshulam, and others. Recently, motivated by some geometric questions, we extended these methods further, and in this talk I’ll explain the ideas and some of our results.

Eun Jung Kim, Tree-cut width: computation and algorithmic applications

February 27th, 2015
Tree-cut width: computation and algorithmic applications
Eun Jung Kim
CNRS, LAMSADE, Paris, France
2015/3/24 Tue 4PM-5PM
Wollan has recently introduced the graph parameter tree-cut width, which plays a similar role with respect to immersions as the graph parameter treewidth plays with respect to minors. Tree-cut width is known to be lower-bounded by a function of treewidth, but it can be much larger and hence has the potential to facilitate the efficient solution of problems which are not believed to be fixed-parameter tractable (FPT) when parameterized by treewidth.
We present a 2-approximation fpt-algorithm for the problem of deciding whether the tree-cut width is at most k: that is, given a graph G and a positive integer k, the algorithm correctly decides in time 2O(k2 log k)·n5 log n that the tree-cut width of G is strictly bigger than k, or returns a tree-cut decomposition whose width is at most 2k. Moreover, we develop the notion of nice tree-cut decompositions and show that any tree-cut decomposition can be transformed into a nice one in polynomial time. Based on this notion, we introduce a general three-stage dynamic framework for the design of FPT algorithms on nice tree-cut decompositions and apply it to several classic problems.
This talk is based on two recent works with Robert Ganian, Stefan Szeider, Sang-il Oum, Christophe Paul, Ignasi Sau and Dimitrios Thilikos.

[Lecture Series] Eric Vigoda, Approximating the Permanent

February 27th, 2015

FYI (Lecture Series)

Approximating the Permanent
Eric Vigoda
College of Computing, Georgia Institute of Technology, Atlanta, GA, USA
2015/3/11 Wed 9AM-10:15AM (E3-1, Room 1501)
I’ll explain the canonical paths method for bounding the mixing time of a
Markov chain. I’ll show the analysis of a Markov chain for generating a
random matching of a graph and its extension for the estimating the
number of perfect matchings of a bipartite graph.

[Lecture Series] Eric Vigoda, Introduction to Markov Chain Monte Carlo Methods

February 27th, 2015

FYI (Lecture Series)

Introduction to Markov Chain Monte Carlo Methods
Eric Vigoda
College of Computing, Georgia Institute of Technology, Atlanta, GA, USA
2015/3/6 Fri 9AM-10:15AM (E3-1, Room 1501)
I’ll introduce Markov chains and their key properties. Then I’ll explain the PageRank algorithm of Brin and Page which is the basis of the Google search engine.

[CS Colloquium] Eric Vigoda, Phase Transitions in Approximate Counting

February 17th, 2015

FYI (CS Colloquium)

Phase Transitions in Approximate Counting
Eric Vigoda
College of Computing, Georgia Institute of Technology, Atlanta, GA, USA
2015/3/2 Mon 4PM-5PM (E3-1, Room 1501)
In this talk we will explain a series of recent works that establish a beautiful connection between the computational complexity of approximate counting problems and statistical physics phase transitions. Our focus is on counting problems such as given a graph with n vertices can we estimate the number of independent sets or k-colorings of this graph in time polynomial in n? We will show that these problems experience a computational phase transition – on one side there is an efficient approximation algorithm and on the other side it is NP-hard to approximate. The critical point for this computational change coincides exactly with a statistical physics phase transition on infinite trees. Our recent work extends these connections to more general models. The key technical contribution is a novel approach for analyzing random regular graphs. This is joint work with Andreas Galanis (Oxford) and Daniel Stefankovic (Rochester) that appeared in STOC ’14.