[Colloquium] 1/14 Talks at TTIC: Pasin Manurangsi, UC Berkeley

[Mary Marre via Colloquium]

When:     Monday, January 14th at *11:00 am*

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

Who:       Pasin Manurangsi, UC Berkeley


*Title*:        Parameterized Inapproximability

*Abstract*: The area of parameterized complexity seeks a more fine-grained
understanding of NP-hard problems by relaxing the notion of efficient
algorithms to the so-called fixed-parameter tractability (FPT). After more
than two decades of work, the parameterized complexity of many fundamental
problems have been classified; that is, each problem is either shown to be
in FPT or shown to be hard for some complexity class that is believed to
not be in FPT. However, for most problems not in FPT, their approximability
statuses remain open. Specifically, there were few techniques to prove
hardness of approximation in the parameterized regime. This has somewhat
changed in the last few years where more tools have been developed to
tackle such problems.

In this talk, I will report on some of our progresses on the area, which
include resolutions to some long-standing open questions in parameterized
complexity.

*Host:*  Madhur Tulsiani <madhurt at ttic.edu>



Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 517*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190107/8d8f624b/attachment.html>