Solving Problems in P given Correlated Instances

Speaker: Dhiraj Holden , MIT CSAIL

Date: Wednesday, December 07, 2016

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

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Pritish Kamath and Akshay Degwekar, MIT CSAIL

Contact: Rebecca Yadegar, ryadegar@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: Dhiraj Holden:Solving Problems in P given Correlated Instances

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.

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Seminar Series 2016/2017.

Created by Rebecca Yadegar at Thursday, November 17, 2016 at 3:12 PM.