<div dir="ltr"><div style="font-size:12.8px"><div class="gmail_default"><font color="#000000" face="arial, helvetica, sans-serif">When:     Wednesday, January 31st <span class="gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il">at</span> <b style="background-color:rgb(255,255,0)">10:30 am </b></font></div><div class="gmail_default"><font color="#000000" face="arial, helvetica, sans-serif"><br></font></div><div class="gmail_default"><font color="#000000" face="arial, helvetica, sans-serif">Where:    <span class="gmail-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"><span class="gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il">TTIC</span></span>, 6045 S Kenwood Avenue, 5th Floor, Room 526</font></div><div class="gmail_default"><font color="#000000" face="arial, helvetica, sans-serif"><br></font></div><div><font color="#000000"><font face="arial, helvetica, sans-serif">Who:       Arturs Backurs, MIT</font></font></div><div><font color="#000000"><span style="font-size:14px"><font face="arial, helvetica, sans-serif"><br></font></span></font></div></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><div>Title:        Below P vs NP: Conditional Quadratic-Time Hardness For Big Data Problems</div><div><br></div><div>Abstract: Many important computational problems have polynomial algorithms, which makes them efficient on instances of moderate or large size. As the data becomes very large, however, those algorithms often run too long even when the runtime exponent is small. For example, a quadratic time algorithm might take hundreds of CPU-years on inputs of gigabyte size. For such inputs one typically needs a (near-)linear algorithm to be efficient. Unfortunately, showing that such algorithms might not exist is difficult because the NP-hardness, the main tool for showing intractability of computational problems, does not make a distinction between problems solvable in linear time and problems that require quadratic time.</div><div><div><br></div><div>In this talk I will give an overview of recent research that aims to remedy this situation. In particular, I will describe quadratic hardness results for problems in string processing (e.g., edit distance computation) and machine learning (e.g., kernel ridge regression or batch gradient computation in neural networks). All of these problems have polynomial time algorithms, but despite extensive amount of research, no near-linear time algorithms have been found. I will show that, under a natural complexity-theoretic conjecture, such algorithms do not exist. I will also show how these lower bounds have inspired the development of efficient algorithms for some variants of these problems.</div></div><div><br></div><span class="gmail-im"><br></span></div><div style="font-size:12.8px">Host: <a href="mailto:cjulia@ttic.edu">Julia Chuzhoy</a></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div><div class="gmail_signature"><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 504</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>