### 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

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.