Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition

DOI10.1137/100816481zbMath1290.68044arXiv1004.3304OpenAlexW2569895586MaRDI QIDQ2839171

Ranganath Kondapally, Graham Cormode, Andrew McGregor, Amit Chakrabarti

Publication date: 4 July 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1004.3304

zbMATH Keywords

lower boundscommunication complexitydata streamsmemory checking

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Statistical aspects of information-theoretic topics (62B10) Randomized algorithms (68W20) Algorithms on strings (68W32)

Related Items (4)

Certifying equality with limited interaction ⋮ Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product ⋮ Everywhere-Tight Information Cost Tradeoffs for Augmented Index ⋮ Quantum Chebyshev's Inequality and Applications

This page was built for publication: Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition