DIMACS Theoretical Computer Science Seminar

Title: Recognizing well-parenthesized expressions in the streaming model

Speaker: Ashwin Nayak, U. Waterloo and Perimeter

Date: Wednesday, April 6, 2011 11:00-12:00pm

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


Motivated by a concrete problem, and with the goal of understanding the relationship between the complexity of streaming algorithms and the computational complexity of formal languages, we investigate the problem Dyck(2) of checking matching parentheses, with two different types of parenthesis.

We present a one-pass randomized streaming algorithm for Dyck(2) with space O(sqrt(n log n)) bits, time per letter polylog(n), and one-sided error. We prove that this one-pass algorithm is optimal, up to a polylog(n) factor, even when two-sided error is allowed. In fact, we show that a similar bound holds for any constant number of passes over the input.

Surprisingly, the space requirement shrinks drastically if we have access to the input stream *in reverse*. We present a two-pass randomized streaming algorithm for Dyck(2) with space O((log n)^2), time polylog(n) and one-sided error, where the second pass is in the reverse direction.

The talk is based on joint work with Frederic Magniez and Claire Mathieu, and with Rahul Jain.