On 20.06.2019 at 12:30 in S6, there is the following noon lecture:
Extensor-Coding: An algebraic Method for hard Graph problems
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.
Webmaster: kamweb.mff.cuni.cz Modified: 25. 02. 2019