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.

Short Bio:
=======

Andrew McGregor is an assistant professor in the Department of Computer Science at the University of Massachusetts, Amherst. He is a member of the theory group and his research is in algorithms and complexity. Specific topics include processing massive data sets and data streams, clustering, approximation algorithms, coding and information theory.
Prior to UMass, he spent a great couple of years at Microsoft Research (Silicon Valley) and the Information Theory and Applications Center at UCSD. In 2007, he received his Ph.D. from the University of Pennsylvania. During graduate school, he spent a summer at DIMACS and three summers at the Fundamental Maths Department at Bell Labs. In the dim and distant past, he received the Certificate of Advanced Study in Mathematics (2001) and a B.A. in Mathematics (2000) from the University of Cambridge.