[Colloquium] REMINDER: 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>*


On Sun, Jan 13, 2019 at 6:31 PM Mary Marre <mmarre at ttic.edu> wrote:

> 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>*
>
>
> On Mon, Jan 7, 2019 at 4:07 PM Mary Marre <mmarre at ttic.edu> wrote:
>
>> 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/20190114/801991ea/attachment-0001.html>