Stable distributions, pseudorandom generators, embeddings, and data stream computation
From MaRDI portal
Publication:3455212
DOI10.1145/1147954.1147955zbMath1326.68161OpenAlexW2045533739MaRDI QIDQ3455212
Publication date: 4 December 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1147954.1147955
Analysis of algorithms and problem complexity (68Q25) Random number generation in numerical analysis (65C10) Theory of data (68P99) Approximation algorithms (68W25)
Related Items (45)
On finding common neighborhoods in massive graphs. ⋮ Sketching and Embedding are Equivalent for Norms ⋮ Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms ⋮ Taylor Polynomial Estimator for Estimating Frequency Moments ⋮ A unified framework for linear dimensionality reduction in L1 ⋮ The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite ⋮ A Statistical Analysis of Probabilistic Counting Algorithms ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Streaming algorithms for language recognition problems ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts ⋮ Sketched approximation of regularized canonical correlation analysis ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Representation and coding of signal geometry ⋮ Single Pass Spectral Sparsification in Dynamic Streams ⋮ Unnamed Item ⋮ Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs ⋮ Multiple Pass Streaming Algorithms for Learning Mixtures of Distributions in ${\mathbb R}^d$ ⋮ Unnamed Item ⋮ Linear dimension reduction approximately preserving a function of the $1$-norm ⋮ A unified scheme for generalizing cardinality estimators to sum aggregation ⋮ Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph ⋮ Tracking the l_2 Norm with Constant Update Time ⋮ Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of L1 ⋮ Continuous Monitoring of l_p Norms in Data Streams ⋮ Graph summarization with quality guarantees ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ Unnamed Item ⋮ The Fast Cauchy Transform and Faster Robust Linear Regression ⋮ Unnamed Item ⋮ Private multiparty sampling and approximation of vector combinations ⋮ Less is More: Sparse Graph Mining with Compact Matrix Decomposition ⋮ The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics ⋮ Multiple pass streaming algorithms for learning mixtures of distributions in \(\mathbb R^d\) ⋮ Periodicity and Cyclic Shifts via Linear Sketches ⋮ Depth First Search in the Semi-streaming Model ⋮ Two Party Distribution Testing: Communication and Security ⋮ Optimality of linear sketching under modular updates ⋮ On Approximating Matrix Norms in Data Streams ⋮ On the Impossibility of Dimension Reduction for Doubling Subsets of $\ell_{p}$ ⋮ Tight Bounds for the Subspace Sketch Problem with Applications ⋮ Perfect $L_p$ Sampling in a Data Stream ⋮ Variance reduction in feature hashing using MLE and control variate method ⋮ Recent advances in text-to-pattern distance algorithms ⋮ Near-neighbor preserving dimension reduction via coverings for doubling subsets of \(\ell_1\)
This page was built for publication: Stable distributions, pseudorandom generators, embeddings, and data stream computation
