The Data Stream Space Complexity of Cascaded Norms

DOI10.1109/FOCS.2009.82zbMath1292.68087OpenAlexW2142224482MaRDI QIDQ5171206

T. S. Jayram, David P. Woodruff

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2009.82

Mathematics Subject Classification ID

Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (9)

Sketching and Embedding are Equivalent for Norms ⋮ A Framework for Adversarially Robust Streaming Algorithms ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Estimating hybrid frequency moments of data streams ⋮ Unnamed Item ⋮ Continuous Monitoring of l_p Norms in Data Streams ⋮ Deterministic Heavy Hitters with Sublinear Query Time ⋮ Streaming Algorithms with One-Sided Estimation

This page was built for publication: The Data Stream Space Complexity of Cascaded Norms