Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminar: Andrew McGregor

LFCS Seminar: Andrew McGregor

— filed under:

Data Streams, Dyck Languages, and Detecting Dubious Data Structures

  • LFCS Seminar
When May 28, 2010
from 04:00 PM to 05:00 PM
Where 4.31/4.33
Add event to calendar vCal

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.

Document Actions