Extensor-Coding

Tóm tắt báo cáo

In this talk, I will give a gentle introduction into algebraic techniques that can be used to solve hard combinatorial problems. In particular, I will show how to use the exterior algebra and related objects in order to detect combinatorial structures in graphs, such as long cycles or more general, small pattern graphs. From the theory of NP-completeness, we know that these problems likely cannot be solved efficiently. However, using advanced techniques such as the ones I show in my talk, we can obtain so-called fixed-parameter algorithms, which are better than brute-force, even though they are still exponential in the worst case. I will assume no deep background in abstract algebra, and start from first principles. This talk is based on joint work with Holger Dell and Thore Husfeldt