The 2017 Paris C. Kanellakis Memorial Lecture


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

Piotr Indyk, MIT

Monday, December 11, 2015 at 4:00 P.M.

Room 368 (CIT 3rd Floor)

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, an 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.

Piotr Indyk is a Professor of Electrical Engineering and Computer Science at MIT. He joined MIT in 2000, after earning PhD from Stanford University and Magister degree from ​Uniwersytet Warszawski in 1995. Piotr’s research interests lie in the design and analysis of efficient algorithms. Specific interests include high-dimensional computational geometry, sketching and streaming algorithms and sparse recovery. He has received the Sloan Fellowship (2003), the Packard Fellowship (2003) and the Simons Investigator Award (2013). His work on Sparse Fourier Transform has been named to Technology Review “TR10” in 2012, while his work on locality-sensitive hashing has received the 2012 ACM Kanellakis Theory and Practice Award.

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

This lecture series honors Paris Kanellakis, a distinguished computer scientist who was an esteemed and beloved member of the Brown Computer Science Department. Paris joined the Computer Science Department in 1981 and became a full professor in 1990. His research area was theoretical computer science, with emphasis on the principles of database systems, logic in computer science, the principles of distributed computing and combinatorial optimization. He died in an airplane crash on December 20,1995, along with his wife, Maria Teresa Otoya, and their two young children, Alexandra and Stephanos Kanellakis.

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

A reception will follow.

Host: Professor Philip Klein