For our final Distinguished Lecture of the spring semester, the CS department is happy to welcome Piotr Indyk from MIT. Indyk will present, Beyond P vs. NP: Quadratic-Time Hardness of Sequence Alignment Problems. Everyone is welcome to join us in Room 120 of the New Computer Science Building at 2:30 for this exciting discussion. Indyk's abstract and bio are presented below.
Abstract
The theory of NP-hardness has been remarkably successful in identifying problems that are unlikely to be solvable in polynomial time. However, many other important problems do have polynomial-time algorithms, but large exponents in their runtime bounds often makes them inefficient in practice. Although for many problems no sub-quadratic time algorithms are known, any evidence of quadratic-time hardness has remained elusive.
Piotr Indyk will present recent research that aims to remedy this situation. In particular, he will focus on the class of problems involving similarity measures between sequences, such as Edit Distance, Frechet Distance and Dynamic Time Warping. These problems have classic quadratic time solutions based on dynamic programming. However, despite extensive amount of research, no strongly subquadratic algorithms for these problems are known. He will show that, under a natural complexity-theoretic conjecture, such subquadratic algorithms do not exist and that strongly sub-quadratic algorithms would violate Strong Exponential Time Hypothesis (SETH), which postulates that satisfiability cannot be solved in "mildly" sub-exponential time. This talks covers from several papers, by Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Kunnemann, Virginia Vassilevska Williams and the speaker.
Biography
Piotr Indyk is a Professor of Electrical Engineering and Computer Science at MIT. He joined MIT in 2000, after earning PhD from Stanford University. Earlier, he received 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 sampling has been named to Technology Review "TR10" in 2012, while his work on locality-sensitive hashing has received the 2012 Kanellakis Theory and Practice Award.
