Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with augmented index:
TR10-076 | 18th April 2010
Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor

Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition

Revisions: 1

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

ISSN 1433-8092 | Imprint