Stable distributions, pseudorandom generators, embeddings and data stream computation

No abstract is available for this paper.

• Publication year

  2000

• Venue

  Proceedings 41st Annual Symposium on Foundations of Computer Science

• Publication date

  2000-11-12

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/SFCS.2000.892082
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• DIMACS Series in Discrete Mathematicsand Theoretical Computer Science Synopsis Data Structures for Massive Data

  2007cited by this paper
• Algorithmic derandomization via complexity theory

  2002cited by this paper
• Derandomized dimensionality reduction with applications

  2002cited by this paper
• Abstract The

  2002cited by this paper
• Maintaining Stream Statistics over Sliding Windows

  2002cited by this paper
• Fast, small-space algorithms for approximate histogram maintenance

  2002cited by this paper
• Dynamic multidimensional histograms

  2002cited by this paper
• Comparing Data Streams Using Hamming Norms (How to Zero In)

  2002cited by this paper
• Fast mining of massive tabular data via approximate distance computations

  2002cited by this paper
• Maintaining stream statistics over sliding windows: (extended abstract)

  2002cited by this paper
• Algorithmic applications of low-distortion geometric embeddings

  2001cited by this paper
• Reductions among high dimensional proximity problems

  2001cited by this paper
• Dimensionality reduction techniques for proximity problems

  2000cited by this paper
• Identifying Representative Trends in Massive Time Series Data Sets Using Sketches

  2000cited by this paper
• Finding interesting associations without support pruning

  2000cited by this paper
• Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces

  1999cited by this paper
• Computing on data streams

  1999cited by this paper
• An Approximate Lp Difference Algorithm for Massive Data Streams

  1999cited by this paper
• Fast hierarchical clustering and other applications of dynamic closest pairs

  1999cited by this paper
• Min-wise independent permutations (extended abstract)

  1998cited by this paper
• Syntactic Clustering of the Web

  1997cited by this paper
• Software reliability via run-time result-checking

  1997cited by this paper
• Dynamic Euclidean minimum spanning trees and extrema of binary functions

  1995cited by this paper
• The geometry of graphs and some of its algorithmic applications

  1994cited by this paper
• Checking approximate computations over the reals

  1993cited by this paper
• The Local Theory of Normed Spaces and its Applications to Convexity

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

  1992influential reference
• Randomized geometric algorithms and pseudorandom generators

  1992cited by this paper
• Conference Proceedings of the Annual ACM Symposium on Theory of Computing

  1992cited by this paper
• The fourth moment method

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

  1990influential reference
• One-dimensional stable distributions

  1986influential reference
• Extensions of Lipschitz mappings into Hilbert space

  1984cited by this paper
• Embeddinglpm intol1n

  1982influential reference
• Random embeddings of Euclidean spaces in sequence spaces

  1981cited by this paper
• Fast Probabilistic Algorithms

  1979cited by this paper
• The dimension of almost spherical sections of convex bodies

  1976influential reference
• A Method for Simulating Stable Random Variables

  1976cited by this paper
• Acta Mathematica

  year unknowncited by this paper

• Continuous Fairness On Data Streams

  2026cites this paper
• Adversarial Robustness on Insertion-Deletion Streams

  2026cites this paper
• Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the \(\boldsymbol{\sqrt {n}}\) Dimension Threshold

  2026cites this paper
• Adaptively Robust Resettable Streaming

  2026cites this paper
• Unbiased Insights: Optimal Streaming Algorithms for ℓp Sampling, the Forget Model, and Beyond

  2025cites this paper
• Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions

  2025influential citation
• On Differential Privacy for Adaptively Solving Search Problems via Sketching

  2025cites this paper
• Even Faster Algorithm for the Chamfer Distance

  2025cites this paper
• On estimating the quantum ℓα distance

  2025cites this paper
• Perfect Sampling in Turnstile Streams Beyond Small Moments

  2025cites this paper
• Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model

  2025cites this paper
• On Sketching Trimmed Statistics

  2025cites this paper
• Federated Data Shift Distance Estimation

  2025cites this paper
• Approximate Spanning Tree Counting from Uncorrelated Edge Sets

  2025cites this paper
• Average Distortion Sketching

  2025cites this paper
• Average-Distortion Sketching

  2024cites this paper
• Turnstile ℓp leverage score sampling with applications

  2024influential citation
• Streaming Algorithms with Few State Changes

  2024cites this paper
• Limitations of the Impagliazzo–Nisan–Wigderson Pseudorandom Generator Against Permutation Branching Programs

  2024cites this paper
• Harmonic Decomposition in Data Sketches

  2024cites this paper
• Fast White-Box Adversarial Streaming Without a Random Oracle

  2024cites this paper
• SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More

  2024cites this paper
• Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold

  2024cites this paper
• UGC: Universal Graph Coarsening

  2024influential citation
• Near-Optimal Dimension Reduction for Facility Location

  2024cites this paper
• Engineering Semi-streaming DFS algorithms

  2024cites this paper
• On the Feasibility of Forgetting in Data Streams

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

  2024influential citation
• Fully Scalable MPC Algorithms for Clustering in High Dimension

  2023cites this paper
• Optimal Sketching Bounds for Sparse Linear Regression

  2023influential citation
• Secure Federated Correlation Test and Entropy Estimation

  2023influential citation
• Private Data Stream Analysis for Universal Symmetric Norm Estimation

  2023cites this paper
• Sampling Big Ideas in Query Optimization

  2023cites this paper
• Large-Scale Distributed Learning via Private On-Device Locality-Sensitive Hashing

  2023cites this paper
• Fast Private Kernel Density Estimation via Locality Sensitive Quantization

  2023cites this paper
• Towards Practical Federated Causal Structure Learning

  2023cites this paper
• A Near-Linear Time Algorithm for the Chamfer Distance

  2023cites this paper
• Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance

  2023cites this paper
• Improved Space Bounds for Learning with Experts

  2023cites this paper
• Electrical Flows for Polylogarithmic Competitive Oblivious Routing

  2023influential citation
• Data Analytics with Differential Privacy

  2023cites this paper
• Differentially Private Continual Releases of Streaming Frequency Moment Estimations

  2023cites this paper
• Random measure priors in Bayesian recovery from sketches

  2023cites this paper
• Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming

  2023cites this paper
• Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions

  2023cites this paper
• Random Projection Based Efficient Detector in Massive MIMO Communication Networks

  2023cites this paper
• Graph Sketch Based Heavy Change Detection for Temporal Network Traffic Analysis

  2023cites this paper
• Finding Missing Items Requires Strong Forms of Randomness

  2023influential citation
• Dynamic Non-monotone Submodular Maximization

  2023cites this paper
• Almost Linear Constant-Factor Sketching for 𝓁1 and Logistic Regression

  2023cites this paper
• A streaming algorithm and hardware accelerator to estimate the empirical entropy of network flows

  2023cites this paper
• Streaming Euclidean k-median and k-means with o(log n) Space

  2023cites this paper
• Robust Algorithms on Adaptive Inputs from Bounded Adversaries

  2023cites this paper
• Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings

  2022cites this paper
• Streaming and Sketching Complexity of CSPs: A survey

  2022cites this paper
• Polylogarithmic Sketches for Clustering

  2022influential citation
• Variance reduction in feature hashing using MLE and control variate method

  2022cites this paper
• Sketching Approximability of (Weak) Monarchy Predicates

  2022cites this paper
• High-Dimensional Geometric Streaming in Polynomial Space

  2022cites this paper
• Distributionally robust scheduling algorithms for total flow time minimization on parallel machines using norm regularizations

  2022cites this paper
• Hitting sets for regular branching programs

  2022cites this paper
• Sketching Distances in Monotone Graph Classes

  2022cites this paper
• Adaptive Segmentation Techniques for Efficient Representation of Time Series Datasets. (Techniques de segmentation adaptative pour une représentation efficace des séries temporelles)

  2022cites this paper
• RL-Shield: Mitigating Target Link-Flooding Attacks Using SDN and Deep Reinforcement Learning Routing Algorithm

  2022cites this paper
• Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly

  2022cites this paper
• Sketch-based entropy estimation: a tabular interpolation approach using P4

  2022cites this paper
• Near-neighbor preserving dimension reduction via coverings for doubling subsets of ℓ1

  2022cites this paper
• Tabular Interpolation Approach Based on Stable Random Projection for Estimating Empirical Entropy of High-Speed Network Traffic

  2022influential citation
• Tensor-Based Sketching Method for the Low-Rank Approximation of Data Streams

  2022cites this paper
• Streaming Euclidean MST to a Constant Factor

  2022influential citation
• Sampling-based Estimation of the Number of Distinct Values in Distributed Environment

  2022cites this paper
• Fast Distance Oracles for Any Symmetric Norm

  2022cites this paper
• Streaming complexity of CSPs with randomly ordered constraints

  2022cites this paper
• Streaming Algorithms with Large Approximation Factors

  2022cites this paper
• F ED -C OR : F EDERATED C ORRELATION T EST WITH S E - CURE A GGREGATION

  2022influential citation
• Identifying Correlation in Stream of Samples

  2022influential citation
• Sketched approximation of regularized canonical correlation analysis

  2022cites this paper
• On Weighted Graph Sparsification by Linear Sketching

  2022cites this paper
• Learning Sparsity and Randomness for Data-driven Low Rank Approximation

  2022cites this paper
• FED-χ2: Privacy Preserving Federated Correlation Test

  2021cites this paper
• Improved Differentially Private Euclidean Distance Approximation

  2021cites this paper
• LogLog Filter: Filtering Cold Items within a Large Range over High Speed Data Streams

  2021cites this paper
• On Efficient Range-Summability of Ideally IID Random Variables in Two or Higher Dimensions

  2021cites this paper
• Differentially Private Frequency Moments Estimation with Polylogarithmic Space

  2021influential citation
• On sketching approximations for symmetric Boolean CSPs

  2021cites this paper
• Monotone Branching Programs: Pseudorandomness and Circuit Complexity

  2021cites this paper
• Pseudorandom Generators for Read-Once Monotone Branching Programs

  2021cites this paper
• Exponentially Improved Dimensionality Reduction for 𝓁1: Subspace Embeddings and Independence Testing

  2021cites this paper
• Separations for Estimating Large Frequency Moments on Data Streams

  2021cites this paper
• Secure Federated Feature Selection

  2021cites this paper
• Closed-form expressions for the sketching approximability of (some) symmetric Boolean CSPs

  2021influential citation
• Improved Pan-Private Stream Density Estimation

  2021cites this paper
• Dimensionality Reduction for Categorical Data

  2021cites this paper
• Approximability of all Boolean CSPs with linear sketches

  2021cites this paper
• New streaming algorithms for high dimensional EMD and MST

  2021cites this paper
• Application of non-Gaussian multidimensional autoregressive model for climate data prediction

  2021cites this paper
• On Efficient Range-Summability of IID Random Variables in Two or Higher Dimensions

  2021cites this paper
• Differentially Private Fractional Frequency Moments Estimation with Polylogarithmic Space

  2021influential citation
• Optimal Streaming Algorithms for Graph Matching

  2021cites this paper
• A Dyadic Simulation Approach to Efficient Range-Summability

  2021influential citation