GROW 2019

Martin Grohe will speak about an unexpected correspondence between a beautiful theory, due to Lovasz, about homomorphisms and graph limits and a popular heuristic for the graph isomorphism problem known as the Weisfeiler-Leman algorithm. He will also relate this to graph kernels in machine learning. Indeed, the context of this work is to desgin and understand similarity measures between graphs and discrete structures.

Based on the joint work with Jan Böker, Holger Dell, and Gaurav Rattan.

Martin Grohe is a Professor of Computer Science at RWTH Aachen University, Germany, renowned for his research on parameterized complexity, graph theory, and mathematical logic, to mention a few. Grohe studied mathematics in Freiburg, received his doctorate there in 1994 and returned to Germany after research stays at the University of California at Santa Cruz and at Stanford University. See also his website here

Daniel Král will start with an overview of width parameters for matroids, relating them to their counterparts for graphs and demonstrating some of their algorithmic applications. He will particularly focus on the parameter called branch-depth, which is the counterpart of tree-depth of a graph. The interest in this parameter comes from the integer programming. There is a strongly fixed parameter algorithm for integer programs with the constraint matrix with bounded dual tree-depth and bounded entries. However, the dual tree-depth of the matrix is not preserved by row operations. He will show that the branch-depth of the column space of the constraint matrix is bounded if and only if the matrix is row-equivalent to a matrix with small dual tree-depth, and discuss how to obtain such a row-equivalent matrix in an algorithmic way. In particular, he establishes the existence of a strongly fixed parameter algorithm for integer programs with the constraint matrix with bounded branch-depth and bounded entries.

The talk is based on results joint with Frantisek Kardos, Anita Liebenau and Lukas Mach, and with Martin Koutecky.

Daniel Král holds the newly established Donald Ervin Knuth Professorship and is a co-leader of the Laboratory of Discrete Methods and Algorithms (DIMEA) at the Faculty of Informatics of Masaryk University in Brno, Czech Republic. He is still a part-time professor of mathematics and computer science and a member of the DIMAP research center, at the University of Warwick. His research work is focused on graph theory and related fields in mathematics and computer science. Král is the recipient of the ERC Consolidator grant LADIST, and ERC Starting grant CCOSA. See also his website here

Meriav Zehavi in this talk focuses on decompositions of geometric graphs. Specifically, she will discuss tree decompositions with special properties for unit disk graphs and map graphs. With respect to applications, she will deploy these decompositions to design subexponential-time and exponential-time parameterized algorithms.

Meriav Zehavi is an assistant professor at the Department of Computer Science at Ben-Gurion University, Israel. Her research interests lie in the fields of kernelization, parameterized algorithms and parameterized complexity, computational geometry, approximation algorithms, computational social choice, and bioinformatics. In the Spring of 2016, she has been hosted by the Simons Institute at Berkley, where she has been researching the topic of Algorithmic Challenges in Genomics. See also her website here