讨论组:学生讲座
标题:On Kernelization of some NP-hard problems
演讲人: 唐邦晟
时间: 2011-04-14 16:30-2011-04-14 17:30
地点:FIT 1-222

内容:

Kernelization is an important tool when designing algorithms for everyday life, especially for those provably NP-hard problems. In this talk, I will first refresh your memory about kernelization, and then present a technique called OR-distillation by Fortnow and Santhanam, which is widely used in proving impossibility of kernalization and some related complexity problems. A specific example is that, Vertex Cover of size k has a kernel of size k^2, but existence of kernelization of size k^{2-\epsilon} will cause polynomial hierarchy collapse.



人物介绍: