Skip to content Skip to navigation
Seminar
4/30/2014 11:00 am
CoRE A(Room 301)

Approximating distance to monotonicity in the streaming setting

Timothy Naumovitz, Rutgers University

Organizer(s): Swastik Kopparty and Shubhangi Saraf

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.