Title: Data Streams, Dyck Languages, and Detecting Dubious Data Structures

Speaker: Andrew McGregor, UMass

Time/Date: Thursday, May 5, 11-12
Location: Room 3402

Abstract:

In this talk, we present algorithms and lower bounds for recognizing
various languages in the data stream model.  In particular, we resolve
an open problem of Magniez, Mathieu and Nayak [STOC, 2010] concerning
the multi-pass complexity of recognizing Dyck languages. This results
in a natural separation between the standard multi-pass model and the
multi-pass model that permits reverse passes. We also present the
first passive memory checkers that verify the interaction transcripts
of priority queues, stacks, and double-ended queues. We obtain tight
upper and lower bounds for these problems, thereby addressing an
important sub-class of the memory checking framework of Blum et
al. [Algorithmica, 1994]. A key contribution of our work is a new
bound on the information complexity of AUGMENTED-INDEX.

Includes joint work with Amit Chakrabarti, Graham Cormode, and
Ranganath Kondapally.