Virginia Vassilevska Williams: Fast distance product of bounded difference matrices with applications to Language Edit Distance and RNA-Folding

Speaker: Virginia Vassilevska Williams, MIT

Date: Tuesday, April 11, 2017

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Refreshments: 3:45 PM

Public: Yes

Location: Patil/Kiva G449

Event Type:

Room Description:

Host: Aleksander Madry

Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Virginia Vassilevska Williams: Fast distance product of bounded difference matrices with applications to Language Edit Distance and RNA-Folding

Abstract:

The distance product of two matrices A and B is the matrix C defined as C[i,j]=min_k A[i,k]+B[k,j].
Computing the distance product of arbitrary n x n matrices is equivalent (wrt worst case runtime) to the All Pairs Shortest Paths problem on n-node graphs, a problem whose best runtime has been notoriously stuck at n^{3-o(1)} for decades. Nevertheless, when A and B are structured, sometimes truly subcubic, O(n^{3-eps}) time, for constant eps>0, algorithms are possible.

An interesting structured case that has so far resisted improvements (and whose best distance product algorithm was not known to take truly subcubic time) is that of bounded difference (BD) matrices. A matrix A is said to be an L- bounded difference (L-BD) matrix if for all i,j: |A[i,j] - A[i,j+1]| <= L and |A[i,j] - A[i+1,j]| <= L. Via an approach of Leslie Valiant, any algorithm for the distance product of O(1)-BD matrices can be used to solve two other very different problems in essentially the same time: RNA-Folding (a problem formalizing how to find the secondary structure of an RNA sequence) and Context Free Language Edit Distance (a problem in which given a context free grammar defining a language L and a string x, one needs to compute the minimum, over all words y in L, of the edit distance between x and y.).

In this talk I will present the first truly subcubic time algorithm for L-BD matrices for small L, thus obtaining the first truly subcubic time algorithms for RNA-Folding and Context Free Language Edit Distance.

Joint work with Karl Bringmann, Fabrizio Grandoni and Barna Saha, in FOCS 2016.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation (TOC) 2017.

Created by Deborah Goodwin at Friday, March 31, 2017 at 2:20 PM.