ELC Seminar (A03)
| Time & Date | Feb. 19(Fri) 2016, 14:00 ~ 16:15 | |
|---|---|---|
| Place | CELC Seminar room (Rm. 404) | |
| Speaker | Hans L. Bodlaender | |
| Title | Kernelization: upper and lower bound techniques | |
| Abstract | ||
|---|---|---|
| In this talk, a survey on the topic of kernelization is given. In the first part, the notion is introduced, and a number of examples of kernelization algorithms are given, and some techniques to obtain kernels are reviewed. In the second part, recent techniques to obtain lower bounds for kernels are surveyed: with help of compositions or cross-compositions, it can be shown for a large collection of problems that these do not have kernels of polynomial size, assuming that coNP is not a subset of NP/poly. (Host: Yota Otachi) |
||