Cover Image

Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kacham, Praneeth, Pagh, Rasmus, Thorup, Mikkel, Woodruff, David P.
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Approximating the Top Eigenvector in Random Order Streams
by: Kacham, Praneeth, et al.
Published: (2024)

Faster Algorithms for Schatten-p Low Rank Approximation
by: Kacham, Praneeth, et al.
Published: (2024)

LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions
by: Kannan, Ravindran, et al.
Published: (2024)

Lower Bounds on Adaptive Sensing for Matrix Recovery
by: Kacham, Praneeth, et al.
Published: (2023)

High-Dimensional Geometric Streaming for Nearly Low Rank Data
by: Esfandiari, Hossein, et al.
Published: (2024)

Optimal Communication for Classic Functions in the Coordinator Model and Beyond
by: Esfandiari, Hossein, et al.
Published: (2024)

Instance-Optimality in PageRank Computation
by: Thorup, Mikkel, et al.
Published: (2025)

Hashing for Sampling-Based Estimation
by: Aamand, Anders, et al.
Published: (2024)

Optimal Non-Adaptive Cell Probe Dictionaries and Hashing
by: Larsen, Kasper Green, et al.
Published: (2023)

Connectivity augmentation is fixed-parameter tractable
by: Korhonen, Tuukka, et al.
Published: (2026)

Modern Minimal Perfect Hashing: A Survey
by: Lehmann, Hans-Peter, et al.
Published: (2025)

Streaming Private Continual Counting via Binning
by: Andersson, Joel Daniel, et al.
Published: (2024)

Pivot based correlation clustering in the presence of good clusters
by: Lolck, David Rasmussen, et al.
Published: (2026)

Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time
by: Jin, Wenyu, et al.
Published: (2024)

Profile Reconstruction from Private Sketches
by: Wu, Hao, et al.
Published: (2024)

Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation
by: Pham, Ninh, et al.
Published: (2025)

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
by: Cohen-Addad, Vincent, et al.
Published: (2025)

A Faster Algorithm for Constrained Correlation Clustering
by: Fischer, Nick, et al.
Published: (2025)

PageRank Centrality in Directed Graphs with Bounded In-Degree
by: Thorup, Mikkel, et al.
Published: (2025)

Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
by: Narayanan, Shyam, et al.
Published: (2024)

Streaming Algorithms with Few State Changes
by: Jayaram, Rajesh, et al.
Published: (2024)

$L_p$ Sampling in Distributed Data Streams with Applications to Adversarial Robustness
by: Lin, Honghao, et al.
Published: (2025)

Perfect Sampling in Turnstile Streams Beyond Small Moments
by: Woodruff, David P., et al.
Published: (2025)

Aleph Filter: To Infinity in Constant Time
by: Dayan, Niv, et al.
Published: (2024)

Faster Private Minimum Spanning Trees
by: Pagh, Rasmus, et al.
Published: (2024)

Space Complexity of Minimum Cut Problems in Single-Pass Streams
by: Ding, Matthew, et al.
Published: (2024)

Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures
by: Ene, Alina, et al.
Published: (2025)

Adversarial Robustness on Insertion-Deletion Streams
by: Gribelyuk, Elena, et al.
Published: (2026)

A Smooth Binary Mechanism for Efficient Private Continual Observation
by: Andersson, Joel Daniel, et al.
Published: (2023)

Estimating Random-Walk Probabilities in Directed Graphs
by: Bertram, Christian, et al.
Published: (2025)

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

Faster All-Pairs Optimal Electric Car Routing
by: Dorfman, Dani, et al.
Published: (2025)

Unbiased Insights: Optimal Streaming Algorithms for $\ell_p$ Sampling, the Forget Model, and Beyond
by: Lin, Honghao, et al.
Published: (2025)

Fast Similarity Sketching
by: Dahlgaard, Søren, et al.
Published: (2017)

Combinatorial Correlation Clustering
by: Cohen-Addad, Vincent, et al.
Published: (2024)

The $\ell_p$-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines
by: Li, Yi, et al.
Published: (2022)

Differentially Private Quantiles with Smaller Error
by: Imola, Jacob, et al.
Published: (2025)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
by: Goranci, Gramoz, et al.
Published: (2023)

Private Lossless Multiple Release
by: Andersson, Joel Daniel, et al.
Published: (2025)