Computer Science – Computational Complexity
Scientific paper
2010-04-19
Computer Science
Computational Complexity
Scientific paper
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].
Chakrabarti Amit
Cormode Graham
Kondapally Ranganath
McGregor Andrew
No associations
LandOfFree
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-471538