Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
Information Cost Tradeoffs For Augmented Index And Streaming Language Recognition, Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew Mcgregor
Information Cost Tradeoffs For Augmented Index And Streaming Language Recognition, Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew Mcgregor
Dartmouth Scholarship
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 …