[Colloquium] REMINDER: 10/26 Young Researcher Seminar Series: Arturs Backurs, MIT

[Mary Marre via Colloquium]

When:     Wednesday, October 26th at 11:00am

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

Who:       Arturs Backurs, MIT


Title:     Conditional Quadratic Hardness for Data Analysis Problems

Abstract:
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.

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.


Host: Yury Makarychev, yury at ttic.edu


************************************************************
*******************************************



The TTIC Young Researcher Seminar Series (http://www.ttic.edu/young-
researcher.php) features talks by Ph.D. students and postdocs whose research is
of broad interest to the computer science community. The series provides an
opportunity for early-career researchers to present recent work to and meet
with students and faculty at TTIC and nearby universities.


The seminars are typically held on Wednesdays at 11:00am in TTIC Room 526.

For additional information, please contact Matthew Walter (mwalter at ttic.edu
).


Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*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/20161025/a4a40976/attachment.html>