Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | future lectures)

On 20.06.2019 at 12:30 in S6, there is the following noon lecture:

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.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 25. 02. 2019