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
Abstract:
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.