Danny Hermelin

Fractals for Kernelization Lower Bounds

VCLA hosted a talk by Danny Hermelin on March 6, 2017

DATE:Monday, March 6, 2017
TIME:11:30 am
VENUE: Seminarraum von Neumann (Favoritenstrasse 11)

ABSTRACT

In this talk I will present a construction that can be used for excluding polynomial kernels for a few parameterized problems of a specific nature. The construction has fractal-like properties, hence the title of the talk. After describing the main ideas behind the construction, I will briefly explain how it can be applied to the Length Bound s,t-Cut problem, resolving an open problem posed by Golovach and Thilikos. The talk will assume only very basic knowledge of parameterized complexity.

Comments are closed.