The Data Stream Space Complexity of Cascaded Norms

No abstract is available for this paper.

• Publication year

  2009

• Venue

  2009 50th Annual IEEE Symposium on Foundations of Computer Science

• Publication date

  2009-10-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/FOCS.2009.82
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• 1-pass relative-error Lp-sampling with applications

  2010cited by this paper
• Coresets and sketches for high dimensional subspace approximation problems

  2010cited by this paper
• Lower bounds for edit distance and product metrics via Poincaré-type inequalities

  2010cited by this paper
• Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND

  2009cited by this paper
• Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness

  2009cited by this paper
• Efficient Sketches for Earth-Mover Distance, with Applications

  2009cited by this paper
• Estimating hybrid frequency moments of data streams

  2008cited by this paper
• Revisiting Norm Estimation in Data Streams

  2008cited by this paper
• Overcoming the ‘ 1 Non-Embeddability Barrier: Algorithms for Product Metrics

  2008cited by this paper
• Efficient and private distance approximation in the communication and streaming models

  2007cited by this paper
• Simpler algorithm for estimating frequency moments of data streams

  2006cited by this paper
• Space efficient mining of multigraph streams

  2005influential reference
• Data streams: algorithms and applications

  2005cited by this paper
• Optimal approximations of the frequency moments of data streams

  2005cited by this paper
• Optimal space lower bounds for all frequency moments

  2004cited by this paper
• An improved data stream summary: the count-min sketch and its applications

  2004cited by this paper
• Near-optimal lower bounds on the multi-party communication complexity of set disjointness

  2003cited by this paper
• Finding frequent items in data streams

  2002cited by this paper
• Abstract The

  2002cited by this paper
• Counting Distinct Elements in a Data Stream

  2002cited by this paper
• An information statistics approach to data stream and communication complexity

  2002cited by this paper
• Lectures on discrete geometry

  2002cited by this paper
• Informational complexity and the direct sum problem for simultaneous message complexity

  2001cited by this paper
• Stable distributions, pseudorandom generators, embeddings and data stream computation

  2000cited by this paper
• Pseudorandom generators for space-bounded computation

  1992cited by this paper
• Pseudorandom generators for space-bounded computations

  1990cited by this paper
• Probabilistic Counting Algorithms for Data Base Applications

  1985cited by this paper

• Learning-Augmented Moment Estimation on Time-Decay Models

  2026influential citation
• Streaming Algorithms with Few State Changes

  2024cites this paper
• Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters

  2024cites this paper
• Sketching, Moment Estimation, and the Lévy-Khintchine Representation Theorem

  2024cites this paper
• Streaming Algorithms with Large Approximation Factors

  2022cites this paper
• Streaming Facility Location in High Dimension via New Geometric Hashing

  2022cites this paper
• Streaming Facility Location in High Dimension via Geometric Hashing

  2022cites this paper
• A simple proof of a new set disjointness with applications to data streams

  2021cites this paper
• Subspace Exploration: Bounds on Projected Frequency Estimation

  2021cites this paper
• Learning-Augmented Data Stream Algorithms

  2020cites this paper
• Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators

  2020cites this paper
• A Framework for Adversarially Robust Streaming Algorithms

  2020influential citation
• WOR and $p$'s: Sketches for $\ell_p$-Sampling Without Replacement

  2020cites this paper
• A Framework for Adversarially Robust Streaming Algorithms

  2020influential citation
• Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension

  2019cites this paper
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, September 20-22, 2019

  2019cites this paper
• LEARNING-AUGMENTED DATA STREAM ALGO-

  2019influential citation
• 18 : 2 Deterministic Heavy Hitters with Sublinear Query Time

  2019cites this paper
• Towards Optimal Moment Estimation in Streaming and Distributed Models

  2019cites this paper
• Lp Samplers and Their Applications

  2019influential citation
• SKETCHING AND EMBEDDING ARE EQUIVALENT FOR

  2018cites this paper
• On Sketching the q to p norms

  2018cites this paper
• Towards a Zero-One Law for Entrywise Low Rank Approximation

  2018cites this paper
• 1 L p Samplers and Their Applications : A Survey GRAHAM CORMODE

  2018influential citation
• Deterministic Heavy Hitters with Sublinear Query Time

  2017cites this paper
• Distributed PCP Theorems for Hardness of Approximation in P

  2017cites this paper
• Continuous monitoring of 𝓁p norms in data streams

  2017cites this paper
• High-dimensional similarity search and sketching: algorithms and hardness

  2017cites this paper
• Sketching Algorithms for Big Data Fall 2017 Lecture 2 — September 5

  2017cites this paper
• Continuous monitoring of $\ell_p$ norms in data streams

  2017cites this paper
• Handbook of Big Data

  2016cites this paper
• Heavy Hitters via Cluster-Preserving Clustering

  2016cites this paper
• New Algorithms for Heavy Hitters in Data Streams (Invited Talk)

  2016cites this paper
• Streaming symmetric norms via measure concentration

  2015cites this paper
• Beating CountSketch for heavy hitters in insertion streams

  2015cites this paper
• Sketching and Embedding are Equivalent for Norms

  2014cites this paper
• Data Streams and Applications in Computer Science

  2014cites this paper
• On the information complexity of cascaded norms with small domains

  2013cites this paper
• (1+ Є)-approximation for facility location in data streams

  2013cites this paper
• A Tight Lower Bound for High Frequency Moment Estimation with Small Error

  2013influential citation
• On the Communication Complexity of Sparse Set Disjointness and Exists-Equal Problems

  2013cites this paper
• Algorithms and lower bounds in the streaming and sparse recovery models

  2012cites this paper
• Sketching and streaming high-dimensional vectors

  2011cites this paper
• Open Problems in Data Streams, Property Testing, and Related Topics

  2011cites this paper
• Streaming Algorithms with One-Sided Estimation

  2011cites this paper
• Non-uniform Sampling in Clustering and Streaming

  2011influential citation
• Near-optimal private approximation protocols via a black box transformation

  2011cites this paper
• Tight bounds for data stream algorithms and communication problems

  2011cites this paper
• Information complexity: a tutorial

  2010cites this paper
• Streaming Algorithms from Precision Sampling

  2010influential citation
• Recursive Sketching For Frequency Moments

  2010cites this paper
• Streaming Algorithms via Precision Sampling

  2010cites this paper
• Coresets and sketches for high dimensional subspace approximation problems

  2010cites this paper
• Tight bounds for Lp samplers, finding duplicates in streams, and related problems

  2010cites this paper
• Fast Manhattan sketches in data streams

  2010cites this paper
• On the exact space complexity of sketching and streaming small norms

  2010cites this paper
• 1-pass relative-error Lp-sampling with applications

  2010cites this paper
• Lower bounds for edit distance and product metrics via Poincaré-type inequalities

  2010cites this paper
• Periodicity in Streams

  2010cites this paper
• Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND

  2009cites this paper
• Efficient Sketches for EarthMover Distance , with Applications

  2009cites this paper
• Efficient Sketches for Earth-Mover Distance, with Applications

  2009cites this paper
• Estimating hybrid frequency moments of data streams

  2008cites this paper