### DIMACS Theoretical Computer Science Seminar

Title: Approximating the longest increasing subsequence in polylogarithmic time

Speaker: **Michael Saks**, Rutgers University

Date: Wednesday, September 8, 2010 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

Finding the longest increasing subsequence (LIS) is
a classic algorithmic problem. Let n denote the size
of the array. Simple O(n log n) algorithms are known for
solving this problem exactly.

While this algorithm runs in nearly linear time, with the increasing
ubiquity of enormous data sets, there has been considerable interest
in developing algorithms for problems like LIS that operate by sampling
the input in a small number of places and obtain good approximations
to the answer.

In this talk I'll discuss recent work of C. Seshadhri
and myself, in which we develop a polylogarithmic time
randomized algorithm that for any constant C > 0,
outputs an approximation to the length of the LIS that (with
high probability) is accurate to within an additive Cn.
Previously, the best known polylogarithmic time algorithms could
achieve only an additive n/2 approximation.

It is not hard to see that uniform random sampling of the input is not
sufficient to get a good approximation to the LIS.
Our algorithm uses random sampling that is both non-uniform and
adaptive (that is the choice of points to sample depends on the values
observed previously.)