![](https://d3ilqtpdwi981i.cloudfront.net/KHab8DRdz98ZQKh7W61apMy45J0=/425x550/smart/https://bepress-attached-resources.s3.amazonaws.com/uploads/3f/c5/a7/3fc5a738-670e-4095-85da-ce2a5417ef3d/thumbnail_BPFile%20object.jpg)
This paper makes three main contributions to the theory of communication complexity and stream computation. First, we present new bounds on the information complexity of AUGMENTED-INDEX. In contrast to analogous results for INDEX by Jain, Radhakrishnan and Sen [J. ACM, 2009], we have to overcome the significant technical challenge that protocols for AUGMENTED-INDEX may violate the “rectangle property” due to the inherent input sharing. Second, we use these bounds to resolve an open problem of Magniez, Mathieu and Nayak [STOC, 2010] that asked about 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. Third, we 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].
Available at: http://works.bepress.com/andrew_mcgregor/2/