Title: Approximating Distance to Monotonicity in the Streaming Setting
Speaker: Timothy Naumovitz, Rutgers University
Date: Wednesday, April 30, 2014 11:00-12:00pm
Location: CoRE Bldg, Room 301A, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Given a sequence of integers, one natural problem that can be considered is the LIS problem, which involves finding the length of their longest increasing subsequence. The complement of this problem is known as the distance to monotonicity problem, with the intuition that the distance to monotonicity of a sequence of integers is the minimum number of values that would have to be altered to make the sequence monotone. While one can look at these problems in other settings, we will focus on the streaming setting, where the sequence of integers is given to us one at a time and the goal is to minimize the amount of space used.
It has been shown by Gopalan, Jayram, Krauthgamer, and Kumar that computing these quantities exactly in the streaming setting cannot be done using sublinear space, so we instead settle for finding a multiplicative approximation. Previously, Saks and Seshadhri found a polylogarithmic space randomized algorithm to approximate distance to monotonicity, and we match this with a polylogarithmic space algorithm in the deterministic case. Additionally, we provide nontrivial lower bounds in both the deterministic and randomized cases, which will be discussed if there is time.
This is joint work with Michael Saks.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S14/