<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-family:arial,sans-serif;font-size:12.8px;font-weight:bold"><font color="#000000" face="arial, helvetica, sans-serif">When: <span style="font-weight:400">    Monday, January 14th </span><span class="gmail-m_-6999367977371938806gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il" style="font-weight:400">at</span><span style="font-weight:400"> </span><b>11:00 am</b></font></div><div class="gmail_default" style="font-family:arial,sans-serif;font-size:12.8px"><font color="#000000" face="arial, helvetica, sans-serif"><br></font></div><div class="gmail_default" style="font-family:arial,sans-serif;font-size:12.8px;font-weight:bold"><font color="#000000" face="arial, helvetica, sans-serif">Where:<span style="font-weight:400">    </span><span class="gmail-m_-6999367977371938806gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-m_8421504075585210435gmail-m_3262824545120381495gmail-m_-1141671822915777344gmail-m_-7219251726624328345gmail-m_-8588148075564318222gmail-m_-8767966813928691312gmail-m_-1542318334608687154gmail-m_5717104778280916634gmail-m_4845490158781220632gmail-m_5124567205141626540gmail-m_3209361100497750746gmail-m_2953668934074478317gmail-m_-3155518689668024534m_9067904842688472155gmail-m_3071693547520408192gmail-il" style="font-weight:400"><span class="gmail-m_-6999367977371938806gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il"><span class="gmail-m_-6999367977371938806gmail-il">TTIC</span></span></span><span style="font-weight:400">, 6045 S Kenwood Avenue, 5th Floor, Room 526</span></font></div><div class="gmail_default" style="font-family:arial,sans-serif;font-size:12.8px"><br></div><div><font color="#000000" style="font-family:arial,sans-serif;font-size:12.8px;font-weight:bold"><font face="arial, helvetica, sans-serif">Who:<span style="font-weight:400">       </span></font></font><font color="#000000" face="arial, helvetica, sans-serif"><span style="font-size:12.8px">Pasin Manurangsi, UC Berkeley</span></font></div><br class="gmail-m_-6999367977371938806gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-Apple-interchange-newline"><br class="gmail-m_-6999367977371938806gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-Apple-interchange-newline"><b style="font-family:arial,sans-serif;font-size:12.8px">Title</b><span style="font-family:arial,sans-serif;font-size:12.8px">:       </span> Parameterized Inapproximability  <br style="font-family:arial,sans-serif;font-size:12.8px"><br style="font-family:arial,sans-serif;font-size:12.8px"><b style="font-family:arial,sans-serif;font-size:12.8px">Abstract</b><span style="font-family:arial,sans-serif;font-size:12.8px">: </span>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. <div><br></div><div>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.<br></div><div><div><font face="arial, sans-serif"><span style="font-size:12.8px"><br></span></font><div><div style="font-family:arial,sans-serif;font-size:12.8px"><b>Host:</b>  <a href="mailto:madhurt@ttic.edu" target="_blank">Madhur Tulsiani</a></div><br class="gmail-Apple-interchange-newline"></div></div></div><div><br></div><div><br></div><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr">On Mon, Jan 7, 2019 at 4:07 PM Mary Marre <<a href="mailto:mmarre@ttic.edu">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div style="font-family:arial,sans-serif;font-size:12.8px;font-weight:bold"><font color="#000000" face="arial, helvetica, sans-serif">When: <span style="font-weight:400">    Monday, January 14th </span><span class="gmail-m_-6999367977371938806gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il" style="font-weight:400">at</span><span style="font-weight:400"> </span><b>11:00 am</b></font></div><div style="font-family:arial,sans-serif;font-size:12.8px;font-weight:400"><font color="#000000" face="arial, helvetica, sans-serif"><br></font></div><div style="font-family:arial,sans-serif;font-size:12.8px;font-weight:bold"><font color="#000000" face="arial, helvetica, sans-serif">Where:<span style="font-weight:400">    </span><span class="gmail-m_-6999367977371938806gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-m_8421504075585210435gmail-m_3262824545120381495gmail-m_-1141671822915777344gmail-m_-7219251726624328345gmail-m_-8588148075564318222gmail-m_-8767966813928691312gmail-m_-1542318334608687154gmail-m_5717104778280916634gmail-m_4845490158781220632gmail-m_5124567205141626540gmail-m_3209361100497750746gmail-m_2953668934074478317gmail-m_-3155518689668024534m_9067904842688472155gmail-m_3071693547520408192gmail-il" style="font-weight:400"><span class="gmail-m_-6999367977371938806gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il"><span class="gmail-m_-6999367977371938806gmail-il">TTIC</span></span></span><span style="font-weight:400">, 6045 S Kenwood Avenue, 5th Floor, Room 526</span></font></div><div style="font-family:arial,sans-serif;font-size:12.8px;font-weight:400"><br></div><div><font color="#000000" style="font-family:arial,sans-serif;font-size:12.8px;font-weight:bold"><font face="arial, helvetica, sans-serif">Who:<span style="font-weight:400">       </span></font></font><font color="#000000" face="arial, helvetica, sans-serif"><span style="font-size:12.8px">Pasin Manurangsi, UC Berkeley</span></font></div><br class="gmail-m_-6999367977371938806gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-Apple-interchange-newline"><br class="gmail-m_-6999367977371938806gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-Apple-interchange-newline"><b style="font-family:arial,sans-serif;font-size:12.8px">Title</b><span style="font-family:arial,sans-serif;font-size:12.8px">:       </span>

Parameterized Inapproximability  <br style="font-family:arial,sans-serif;font-size:12.8px"><br style="font-family:arial,sans-serif;font-size:12.8px"><b style="font-family:arial,sans-serif;font-size:12.8px">Abstract</b><span style="font-family:arial,sans-serif;font-size:12.8px">: </span>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. <div><br></div><div>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.<br></div><div><div><font face="arial, sans-serif"><span style="font-size:12.8px"><br></span></font><div><div style="font-family:arial,sans-serif;font-size:12.8px"><b>Host:</b>  <a href="mailto:madhurt@ttic.edu" target="_blank">Madhur Tulsiani</a></div><div style="font-family:arial,sans-serif;font-size:12.8px"><br></div><br class="gmail-m_-6999367977371938806gmail-m_8517121454174849988gmail-Apple-interchange-newline"></div><br class="gmail-m_-6999367977371938806gmail-Apple-interchange-newline"><div><div dir="ltr" class="gmail-m_-6999367977371938806gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>
</blockquote></div></div>