Image de couverture de livre

Optimally detecting uniformly-distributed $\ell_2$ heavy hitters in data streams

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Velusamy, Santhoshini, Yu, Huacheng
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes
par: Velusamy, Santhoshini
Publié: (2025)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
par: Sharma, Amatya, et autres
Publié: (2026)

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
par: Sharma, Amatya, et autres
Publié: (2026)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
par: Singer, Noah G., et autres
Publié: (2026)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
par: Hwang, Samuel, et autres
Publié: (2024)

Cuckoo Heavy Keeper and the balancing act of maintaining heavy hitters in stream processing
par: Ngo, Vinh Quang, et autres
Publié: (2024)

Sketching approximations and LP approximations for finite CSPs are related
par: Singer, Noah G., et autres
Publié: (2025)

Streaming approximation resistance of every ordering CSP
par: Singer, Noah G., et autres
Publié: (2021)

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
par: Saxena, Raghuvansh R., et autres
Publié: (2024)

A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates
par: Sawettamalya, Pachara, et autres
Publié: (2025)

A Strong Separation for Adversarially Robust $\ell_0$ Estimation for Linear Sketches
par: Gribelyuk, Elena, et autres
Publié: (2024)

Linear Space Streaming Lower Bounds for Approximating CSPs
par: Chou, Chi-Ning, et autres
Publié: (2021)

Optimal Static Dictionary with Worst-Case Constant Query Time
par: Hu, Yang, et autres
Publié: (2024)

Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
par: Gribelyuk, Elena, et autres
Publié: (2025)

Static Retrieval Revisited: To Optimality and Beyond
par: Hu, Yang, et autres
Publié: (2025)

Testing frequency distributions in a stream
par: Mathieu, Claire, et autres
Publié: (2023)

Near-Optimal Relative Error Streaming Quantile Estimation via Elastic Compactors
par: Gribelyuk, Elena, et autres
Publié: (2024)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
par: Jiang, Cheng, et autres
Publié: (2026)

Adversarial Robustness on Insertion-Deletion Streams
par: Gribelyuk, Elena, et autres
Publié: (2026)

$\ell_2/\ell_2$ Sparse Recovery via Weighted Hypergraph Peeling
par: Fischer, Nick, et autres
Publié: (2025)

Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation
par: Munteanu, Alexander, et autres
Publié: (2024)

A $2\ell k$ Kernel for $\ell$-Component Order Connectivity
par: Kumar, Mithilesh, et autres
Publié: (2016)

Unbiased Insights: Optimal Streaming Algorithms for $\ell_p$ Sampling, the Forget Model, and Beyond
par: Lin, Honghao, et autres
Publié: (2025)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
par: Makarychev, Yury, et autres
Publié: (2024)

Minimizing $\ell_2$ Norm of Flow Time by Starvation Mitigation
par: Kuo, Tung-Wei
Publié: (2021)

Permutation patterns in streams
par: Berendsohn, Benjamin Aram
Publié: (2025)

On Finding $\ell$-th Smallest Perfect Matchings
par: Maalouly, Nicolas El, et autres
Publié: (2025)

Dynamic Metric Embedding into $\ell_p$ Space
par: Banihashem, Kiarash, et autres
Publié: (2024)

Engineering Semi-streaming DFS algorithms
par: Bhagavan, Kancharla Nikhilesh, et autres
Publié: (2024)

Algorithms and Hardness Results for the $(k,\ell)$-Cover Problem
par: Madani, Amirali, et autres
Publié: (2025)

Faster Approximate Fixed Points of $\ell_\infty$-Contractions
par: Feodorov, Andrei, et autres
Publié: (2026)

Local Gibbs sampling beyond local uniformity
par: Liu, Hongyang, et autres
Publié: (2025)

Stable coresets: Unleashing the power of uniform sampling
par: Carmel, Amir, et autres
Publié: (2025)

SimiSketch: Efficiently Estimating Similarity of streaming Multisets
par: Dong, Fenghao, et autres
Publié: (2024)

Faster Semi-streaming Matchings via Alternating Trees
par: Mitrović, Slobodan, et autres
Publié: (2024)

Near-Optimal Constructive Bounds for $\ell_2$ Prefix Discrepancy and Steinitz Problems via Affine Spectral Independence
par: Dutta, Kunal, et autres
Publié: (2026)

Downstream: efficient cross-platform algorithms for fixed-capacity stream downsampling
par: Yang, Connor, et autres
Publié: (2025)

Efficient stream-based Max-Min diversification with minimal failure rate
par: Kalogeratos, Argyris, et autres
Publié: (2020)

The $\ell_p$-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines
par: Li, Yi, et autres
Publié: (2022)

Optimal detection of dissipation in Lindbladian dynamics
par: Cai, Yiyi
Publié: (2026)