[Colloquium] REMINDER: 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>*

On Wed, Jan 24, 2018 at 2:42 PM, Mary Marre <mmarre at ttic.edu> wrote:

> 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 <(773)%20834-1757>*
> *f: (773) 357-6970 <(773)%20357-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/20180130/255e2bcb/attachment.html>