Copertina

Unbiased Insights: Optimal Streaming Algorithms for $\ell_p$ Sampling, the Forget Model, and Beyond

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Lin, Honghao, Nguyen, Hoai-An, Swartworth, William, Woodruff, David P.
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Sharper Bounds for $\ell_p$ Sensitivity Sampling
di: Woodruff, David P., et al.
Pubblicazione: (2023)

Fast Sampling Based Sketches for Tensors
di: Swartworth, William, et al.
Pubblicazione: (2024)

Tight Sampling Bounds for Eigenvalue Approximation
di: Swartworth, William, et al.
Pubblicazione: (2024)

Perfect $L_p$ Sampling with Polylogarithmic Update Time
di: Swartworth, William, et al.
Pubblicazione: (2025)

Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation
di: Woodruff, David P., et al.
Pubblicazione: (2024)

Coresets for Multiple $\ell_p$ Regression
di: Woodruff, David P., et al.
Pubblicazione: (2024)

On Sketching Trimmed Statistics
di: Lin, Honghao, et al.
Pubblicazione: (2025)

Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model
di: Feng, Shiyuan, et al.
Pubblicazione: (2025)

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

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
di: Makarychev, Yury, et al.
Pubblicazione: (2024)

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

A Strong Separation for Adversarially Robust $\ell_0$ Estimation for Linear Sketches
di: Gribelyuk, Elena, et al.
Pubblicazione: (2024)

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

Dynamic Metric Embedding into $\ell_p$ Space
di: Banihashem, Kiarash, et al.
Pubblicazione: (2024)

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

Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms
di: Li, Yi, et al.
Pubblicazione: (2024)

Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation
di: Munteanu, Alexander, et al.
Pubblicazione: (2024)

Streaming Complexity Separations for Dense and Sparse Graphs
di: Liu, Yang P., et al.
Pubblicazione: (2026)

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

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

Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
di: Gribelyuk, Elena, et al.
Pubblicazione: (2025)

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

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

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

Turnstile $\ell_p$ leverage score sampling with applications
di: Munteanu, Alexander, et al.
Pubblicazione: (2024)

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

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

Simultaneously Approximating All $\ell_p$-norms in Correlation Clustering
di: Davies, Sami, et al.
Pubblicazione: (2023)

Fast Dimensionality Reduction from $\ell_2$ to $\ell_p$
di: Chiclana, Rafael, et al.
Pubblicazione: (2025)

The Power of Recursive Embeddings for $\ell_p$ Metrics
di: Krauthgamer, Robert, et al.
Pubblicazione: (2025)

On Approximability of Steiner Tree in $\ell_p$-metrics
di: Fleischmann, Henry, et al.
Pubblicazione: (2023)

Fast Nearest Neighbor Search for $\ell_p$ Metrics
di: Krauthgamer, Robert, et al.
Pubblicazione: (2026)

Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
di: Kacham, Praneeth, et al.
Pubblicazione: (2023)

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

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
di: Cheng, Yu, et al.
Pubblicazione: (2024)

Iterative Refinement for $\ell_p$-norm Regression
di: Adil, Deeksha, et al.
Pubblicazione: (2019)

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

Learning the Positions in CountSketch
di: Li, Yi, et al.
Pubblicazione: (2023)

Online Correlation Clustering: Simultaneously Optimizing All $\ell_p$-norms
di: Davies, Sami, et al.
Pubblicazione: (2025)