School of Technology and Computer Science Seminars

Fast Subset Convolution for Exact Exponential Algorithms

by Siddharth Bhandari (School of Technology and Computer Science, TIFR)

Friday, February 10, 2017 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
I will present a technique know as fast subset convolution for Exact Exponential Algorithms. We will see how this technique immediately gives algorithms for a bunch of coloring and covering problems on graphs, and in particular solves the problem of finding the chromatic number of a graph in O*(2^n) time, which was open till 2006. (Björklund and Husfeldt, FOCS 2006)