Cover Image

A Unified Construction of Streaming Sketches via the Lévy-Khintchine Representation Theorem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Pettie, Seth, Wang, Dingyu
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Probability
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Universal Perfect Samplers for Incremental Streams
by: Pettie, Seth, et al.
Published: (2024)

Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon
by: Pettie, Seth, et al.
Published: (2020)

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
by: Long, Yaowei, et al.
Published: (2024)

The Squishy Grid Problem
by: Cai, Zixi, et al.
Published: (2025)

Space Complexity of Vertex Connectivity Oracles
by: Pettie, Seth, et al.
Published: (2022)

Harmonic Decomposition in Data Sketches
by: Wang, Dingyu
Published: (2024)

Comparison Theorems for the Mixing Times of Systematic and Random Scan Dynamics
by: Gaitonde, Jason, et al.
Published: (2024)

Semirandom Planted Clique via 1-norm Isometry Property
by: Guruswami, Venkatesan, et al.
Published: (2025)

Subquadratic Counting via Perfect Marginal Sampling
by: Chen, Xiaoyu, et al.
Published: (2026)

Near-Optimal Parallel Approximate Counting via Sampling
by: Harris, David G., et al.
Published: (2026)

Optimal Protocols for 2-Party Contention Resolution
by: Wang, Dingyu
Published: (2024)

Multi-dimensional Approximate Counting
by: Wang, Dingyu
Published: (2024)

Sketching and Streaming for Dictionary Compression
by: Becker, Ruben, et al.
Published: (2023)

A Sampling Lovász Local Lemma for Large Domain Sizes
by: Wang, Chunyang, et al.
Published: (2023)

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
by: Huang, Shang-En, et al.
Published: (2016)

Rapid Mixing via Coupling Independence for Spin Systems with Unbounded Degree
by: Chen, Xiaoyu, et al.
Published: (2024)

A Bicriterion Concentration Inequality and Prophet Inequalities for $k$-Fold Matroid Unions
by: Alon, Noga, et al.
Published: (2024)

Sampling Proper Colorings on Line Graphs Using $(1+o(1))Δ$ Colors
by: Wang, Yulin, et al.
Published: (2023)

Discrete Optimal Transport: Rapid Convergence of Simulated Annealing Algorithms
by: He, Yuchen, et al.
Published: (2026)

Decay of correlation for edge colorings when $q>3Δ$
by: Chen, Zejia, et al.
Published: (2025)

A new notion of commutativity for the algorithmic Lovász Local Lemma
by: Harris, David G., et al.
Published: (2020)

Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains
by: Liu, Kuikui, et al.
Published: (2024)

Constructive l2-Discrepancy Minimization with Additive Deviations
by: Dutta, Kunal
Published: (2025)

Robust recovery for stochastic block models, simplified and generalized
by: Mohanty, Sidhanth, et al.
Published: (2024)

Reconstruction of geometric random graphs with the Simple algorithm
by: Stegehuis, Clara, et al.
Published: (2024)

On Sampling from Ising Models with Spectral Constraints
by: Galanis, Andreas, et al.
Published: (2024)

Convergence Properties of the Asynchronous Maximum Model
by: Larkin, John
Published: (2024)

Mean-field Potts and random-cluster dynamics from high-entropy initializations
by: Blanca, Antonio, et al.
Published: (2024)

The Probability to Hit Every Bin with a Linear Number of Balls
by: Walzer, Stefan
Published: (2024)

Spectral Independence Beyond Total Influence on Trees and Related Graphs
by: Chen, Xiaoyu, et al.
Published: (2024)

Hardness of sampling solutions from the Symmetric Binary Perceptron
by: Alaoui, Ahmed El, et al.
Published: (2024)

Rapid Mixing at the Uniqueness Threshold
by: Chen, Xiaoyu, et al.
Published: (2024)

Counterexamples to a Weitz-Style Reduction for Multispin Systems
by: Liu, Kuikui, et al.
Published: (2024)

Distance Estimation for High-Dimensional Discrete Distributions
by: Kumar, Gunjan, et al.
Published: (2023)

Mixing of general biased adjacent transposition chains
by: Gheissari, Reza, et al.
Published: (2025)

Spectral Alignment of Correlated Gaussian matrices
by: Ganassali, Luca, et al.
Published: (2019)

Rapid Mixing on Random Regular Graphs beyond Uniqueness
by: Chen, Xiaoyu, et al.
Published: (2025)

Planted clique recovery in random geometric graphs
by: Avrachenkov, Konstantin, et al.
Published: (2025)

Sampling Sphere Packings with Continuum Glauber Dynamics
by: Kuchukova, Aiya, et al.
Published: (2026)

The Mixed Birth-death/death-Birth Moran Process
by: Brewster, David A., et al.
Published: (2025)