Skip to main content
Unpublished Paper
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition
(2010)
  • Amit Chakrabarti
  • Graham Cormode
  • Ranganath Kondapally
  • Andrew McGregor, University of Massachusetts - Amherst
Abstract

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].

Disciplines
Publication Date
2010
Comments
This is the pre-published version harvested from arXiv.
Citation Information
Amit Chakrabarti, Graham Cormode, Ranganath Kondapally and Andrew McGregor. "Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition" (2010)
Available at: http://works.bepress.com/andrew_mcgregor/2/