ARC-TRIAD Colloquium: Piotr Indyk (MIT)

Algorithms & Randomness Center (ARC) and TRIAD

Piotr Indyk (MIT)

Monday, March 5, 2018

Klaus 1116 East - 11am


Title:   "Below P vs. NP: Conditional Quadratic-Time Hardness for Big Data Problems"


The theory of NP-hardness has been very successful in identifying problems that are unlikely to have general purpose polynomial time algorithms. However, many other important problems do have polynomial time algorithms, but large exponents in their time bounds can make them run for days, weeks or more. For example, quadratic time algorithms, although practical on moderately sized inputs, can become inefficient on problems that involve gigabytes or more of data. Although for many problems no subquadratic time algorithms are known, 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 describe hardness results for problems in string processing (e.g., edit distance computation or regular expression matching) and machine learning (e.g., support vector machines or batch gradient computation in neural networks). All of them have polynomial time algorithms, but despite an extensive amount of research, no near-linear time algorithms have been found for many variants of these problems. I will show that, under a natural complexity-theoretic conjecture, such algorithms do not exist. I will also describe how this framework has led to the development of new algorithms.


Speaker's webpage

Videos of recent talks are available at:

Click here to subscribe to the seminar email list:


Event Details


  • Monday, March 5, 2018
    11:00 am - Tuesday, March 6, 2018
    11:59 am
Location: Klaus 1116E