Everywhere-Tight Information Cost Tradeoffs for Augmented Index

DOI10.1007/978-3-642-22935-0_38zbMath1343.68292OpenAlexW140986276MaRDI QIDQ3088117

Amit Chakrabarti, Ranganath Kondapally

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22935-0_38

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Network protocols (68M12)

Related Items (1)

Certifying equality with limited interaction

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An information statistics approach to data stream and communication complexity
• On data structures and asymmetric communication complexity
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition
• Recognizing well-parenthesized expressions in the streaming model
• The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: The Index Function Revisited
• A property of quantum relative entropy with an application to privacy in quantum communication
• Graph Distances in the Data-Stream Model
• Communication Complexity
• Numerical linear algebra in the streaming model
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness
• Lower Bounds for Sparse Recovery

This page was built for publication: Everywhere-Tight Information Cost Tradeoffs for Augmented Index