ARC-TRIAD Colloquium: Piotr Indyk (MIT)

Event Details
  • Date/Time:
    • Monday March 5, 2018 - Tuesday March 6, 2018
      11:00 am - 11:59 am
  • Location: Klaus 1116E
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: "Below P vs. NP: Conditional Quadratic-Time Hardness for Big Data Problems" - Klaus 1116E at 11am

Full Summary: No summary paragraph submitted.

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:


Additional Information

In Campus Calendar

Institute for Data Engineering and Science

Invited Audience
Faculty/Staff, Public, Undergraduate students
No keywords were submitted.
  • Created By: Jennifer Salazar
  • Workflow Status: Published
  • Created On: Aug 9, 2018 - 1:37pm
  • Last Updated: Aug 9, 2018 - 1:38pm