Extensor-Coding: An algebraic Method for hard Graph problems

Cornelius Brand

Abstract

In this talk, I will give an introduction to the recent technique of Extensor-Codin (Brand, Dell, Husfeldt, STOC'18) that can be used to solve hard subgraph problems (such as counting approximately the number of paths of given length in a graph, determining existence of spanning trees with few inner nodes, or determining existence of certain colorful subgraphs) faster than previously possible. The technique is based on a rather abstract algebraic object, the exterior algebra, to which I will give a very gentle introduction, and I will sketch how to use it to solve the longest path problem.