<div dir="ltr"><div><div style="font-size:12.8px"><span style="font-family:arial,helvetica,sans-serif;font-size:12.8px">When:</span><span style="font-family:arial,helvetica,sans-serif;font-size:12.8px">     Wednesday, October 26th at </span><span style="font-family:arial,helvetica,sans-serif;font-size:12.8px">11:00am</span><br></div><div style="font-size:12.8px"><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif" style="font-size:12.8px"><span style="font-size:12.8px"><br></span><span style="font-size:12.8px">Where:    TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</span><span style="font-size:12.8px"><br><br></span><span style="font-size:12.8px">Who:   </span></font><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif">    Arturs Backurs, MIT</span></div><div><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif"><br></span></div></div></div><div><br></div><div style="font-size:12.8px">Title:     <span style="font-size:12.8px">Conditional Quadratic Hardness for Data Analysis Problems</span></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Abstract:</div><div style="font-size:12.8px"><span style="font-size:12.8px">The theory of NP-hardness has been remarkably successful in identifying problems that are unlikely to be solvable in polynomial time. However, many other important problems do have polynomial-time algorithms, but large exponents in their runtime bounds can make them inefficient in practice. For example, quadratic-time algorithms, although practical on moderately sized inputs, can become inefficient on big data problems that involve gigabytes or more of data. Although for many data analysis problems no sub-quadratic time algorithms are known, any evidence of quadratic-time hardness has remained elusive.</span><br></div><div style="font-size:12.8px"><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 outline conditional hardness results for two problems: computing the edit distance between two strings, and solving the optimization problems defined by Support Vector Machines (with Gaussian kernel) up to high accuracy. Specifically, we show that, if either of these two problems can be solved in time O(n^{2-delta}) for some constant delta>0, then the satisfiability of conjunctive normal form formulas with N variables and M clauses can be solved in time M^{O(1)} 2^{(1-epsilon)N} for a constant epsilon>0. The latter result would violate the Strong Exponential Time Hypothesis, which postulates that such algorithms do not exist.</div><div><br></div><div><br></div><div>Host: Yury Makarychev, <font color="#0000ff"><a href="mailto:yury@ttic.edu"><span style="font-family:"normal arial",sans-serif;font-size:12px">yury</span><wbr style="font-family:"normal arial",sans-serif;font-size:12px"><span style="font-family:"normal arial",sans-serif;font-size:12px">@ttic.edu</span></a></font></div><div><br></div><div><br></div><div><div style="font-size:12.8px"><span style="font-family:arial,helvetica,sans-serif;font-size:12.8px">*******************************************************************************************************</span><br></div><div style="font-size:12.8px"><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px"><font face="arial, helvetica, sans-serif">The TTIC <span class="gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il">Young</span> <span class="gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il">Researcher</span> Seminar <span class="gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il"><wbr>Series</span> (<a href="http://www.ttic.edu/young-researcher.php" target="_blank">http://www.ttic.edu/yo<wbr>ung-<span class="gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il">researcher</span>.php</a>) features talks by Ph.D. students and postdocs whose <span class="gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il">research</span> is of broad interest to the computer science community. The <span class="gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il">series</span> provides an opportunity for early-career <span class="gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il">researchers</span> to present recent work to and meet with students and faculty at TTIC and nearby universities.</font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px"><font face="arial, helvetica, sans-serif"><br>The seminars are typically held on Wednesdays at 11:00am in TTIC Room 526.<br><br>For additional information, please contact Matthew Walter (<a href="mailto:mwalter@ttic.edu" target="_blank">mwalter@ttic.edu</a>).</font></p><div><font face="arial, helvetica, sans-serif"><br></font></div></div></div><div><br></div><div><br></div><div><br></div><div><br></div></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>