Fine-Grained Rough Draft

Speaker: Petteri Kaski

Finding Outlier Correlations

This talk will look at an algorithm of G. Valiant [FOCS'12, JACM’15] and our recent improvement of the algorithm [SODA’16, to appear] for finding strongly correlated pairs of variables among a collection of n variables with otherwise weak pairwise correlations. After normalization, this task amounts to the geometric task where we are given as input a set of n vectors with unit Euclidean norm and dimension d, and we are asked to find all the outlier pairs of vectors whose inner product is at least r in absolute value, subject to the promise that all but at most q pairs of vectors have inner product at most t in absolute value for some constants 0<t<r<1.

Joint work with Matti Karppa and Jukka Kohonen.

Speaker: Marcin Pilipczuk

A Rough Talk on a Polynomial Kernel for Chordal Vertex Deletion

The input to a graph modification problem is a graph G and an integer k, and we ask to turn G into a graph from a fixed graph class P by at most k modifications; both the target graph class and the allowed modifications (e.g., vertex deletion, edge deletion or addition, edge contraction) are part of the problem definition. The study of graph modification problems with k as a parameter has played an important role in parameterized complexity for the last two decades.

The graph modification problems turn out to be both particularly interesting and challenging for graph classes P being chordal, interval, or similar graph classes. Recall that during the recent workshop with my brother Michał we discussed the case of the completion (edge addition) problems to these graph classes. In this talk I would like to discuss a "fresh from the oven" result for a related graph modification problem, namely Chordal Vertex Deletion (delete k vertices to get a chordal graph). During the last two months of our stay at the Simons Institute, with Bart Jansen we developed a polynomial kernel for this problem.

In the talk I plan to roughly discuss the background for this research and give a rough sketch of the kernel. The talk is intended to roughly meet the high standards set by Marco during the previous seminar.