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)
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) |