Keynote speakers
Barna Saha (University of California Berkeley)
Title: Efficient Fine-grained AlgorithmsAbstract: From its inception, complexity theory through concepts such as NP-Hardness has classified computational problems into those that have relatively efficient solutions versus those that are intractable. Any problem solvable in time polynomial in the input size falls in the first category. However, this crude distinction of algorithmic efficiency is clearly insufficient when handling today's large scale of data. We need a finer-grained design and analysis of algorithms that pinpoints the exact exponent of polynomial running time, and a better understanding of when a speed-up is not possible. While there is a rich history of designing approximation algorithms for NP-hard problems, a similar theory for high polynomial time problems to understand the trade-off between quality and running time is vastly lacking. In this presentation, I will give you an overview of the newly growing field of fine-grained algorithms especially from the viewpoint of developing approximation algorithms. This will include fundamental problems such as edit distance computation, all-pairs shortest paths, parsing and matrix multiplication.
Karl Bringmann (Max-Planck-Institut für Informatik)
Title: Fine-Grained Complexity on StringsAbstract: "Fine-grained complexity" is the design of reductions in order to prove "conditional lower bounds", that is, running time lower bounds that hold under a plausible hypothesis. This area has been flourishing in the last ~5 years, more precisely since the first lower bounds based on the Strong Exponential Time Hypothesis for problems in P. In this talk, we will discuss this development with a focus on string algorithms, specifically on pattern matching and longest common subsequence. Besides the classic setting, we will also look into grammar-compressed strings.
Thore Husfeldt (IT University of Copenhagen and Lund University)
Title: Algebraic algorithms for finding patterns in graphs.Abstract: I will give a gentle introduction to algebraic graph algorithms by showing how to determine if a given graph contains a simple path of length k. This is a famous problem admitting a beautiful and widely-known algorithm, namely the colour-coding method of Alon, Yuster and Zwick (1995). Starting from this entirely combinatorial approach, I will carefully develop an algebraic perspective on the same problem. First, I will explain how the colour-coding algorithm can be understood as the evaluation of a well-known expression (sometimes called the "walk-sum" of the graph) in a commutative algebra called the zeon algebra. From there, I will introduce the exterior algebra and present the algebraic framework recently developed with Brand and Dell (2018). The presentation is aimed at a combinatorially-minded audience largely innocent of abstract algebra.