Solving Problems in P given Correlated Instances

Wednesday, December 7, 2016 - 4:00pm to 5:00pm
Dhiraj Holden

Abstract:Instances of computational problems do not arise in isolation. Often, correlations between the solutions of related instances arise in nature. We study the impact of having access to correlated instances on how fast we can solve a variety of problems. In particular, we look at the longest common subsequence, edit distance, and dynamic time warping distance problems, all of which cannot be solved in time n^{2 - epsilon} assuming the Strong Exponential Time Hypothesis. We give results for two correlation models, a model where the solution corresponds exactly to structure in the correlated instances, and one where each part of the solution is used in the correlated instance with high probability. In both cases we are able to achieve strongly subquadratic time algorithms, and when we have an exact correspondence in the solutions we can solve all of these problems in near-linear time. We view our work as pointing out a new avenue for looking for significant improvements for sequence alignment problems and computing similarity measures, by taking advantage of access to sequences which are correlated through natural generating processes. In this first work we show how to take advantage of mathematically inspired simple clean models of correlation -- the intriguing question, looking forward, is to find correlation models which coincide with evolutionary models and other relationships and for which our approach to multiple sequence alignment gives provable guarantees.

Joint work with Shafi Goldwasser. Paper available at ECCC TR16-056.