# Theory of Computing Seminar

**Fast distance product of bounded difference matrices with applications to language edit distance and RNA folding **

**Speaker:**Virginia Vassilevska Williams, Stanford

**Location:**Annenberg 213

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 is not known to take

truly subcubic time) is that of bounded differences (BDD) matrices.

A matrix A is said to be an L- bounded difference (L-BDD) 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 distance

product of O(1)-BDD 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 work we design the first truly subcubic algorithm for L-BDD

matrices for small L, thus obtaining the first truly subcubic

algorithms for RNA folding and Context Free Language Edit Distance.

**Series**Theory of Computing Seminar Series

**Contact:** Thomas Vidick vidick@cms.caltech.edu