[Colloquium] 1/31 Talks at TTIC: Arturs Backurs, MIT

[Mary Marre via Colloquium]

When:     Wednesday, January 31st at *10:30 am *

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

Who:       Arturs Backurs, MIT


Title:        Below P vs NP: Conditional Quadratic-Time Hardness For Big
Data Problems

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.

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.


Host: Julia Chuzhoy <cjulia 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/20180124/559dda08/attachment.html>