University of Massachusetts, Amherst
4pm Friday, 28th May, 2010
Room 4.31/33, Informatics Forum
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. In contrast to analogous results for INDEX by Jain, Radhakrishnan and Sen [J. ACM, 2009], proving this new bound requires overcoming the significant technical challenge that protocols for AUGMENTED-INDEX may violate the ¡Èrectangle property¡É due to the inherent input sharing.
Joint work with Amit Chakrabarti, Graham Cormode, and Ranganath Kondapally.