:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Velusamy, Santhoshini, Yu, Huacheng
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	https://arxiv.org/abs/2509.07286
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Characterizing Streaming Decidability of CSPs via Non-Redundancy
by: Sharma, Amatya, et al.
Published: (2026)

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
by: Sharma, Amatya, et al.
Published: (2026)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
by: Singer, Noah G., et al.
Published: (2026)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
by: Hwang, Samuel, et al.
Published: (2024)

Sketching approximations and LP approximations for finite CSPs are related
by: Singer, Noah G., et al.
Published: (2025)

Streaming approximation resistance of every ordering CSP
by: Singer, Noah G., et al.
Published: (2021)

Cuckoo Heavy Keeper and the balancing act of maintaining heavy hitters in stream processing
by: Ngo, Vinh Quang, et al.
Published: (2024)

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
by: Saxena, Raghuvansh R., et al.
Published: (2024)

A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates
by: Sawettamalya, Pachara, et al.
Published: (2025)

Linear Space Streaming Lower Bounds for Approximating CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)

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

Optimal Static Dictionary with Worst-Case Constant Query Time
by: Hu, Yang, et al.
Published: (2024)

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

Static Retrieval Revisited: To Optimality and Beyond
by: Hu, Yang, et al.
Published: (2025)

Near-Optimal Relative Error Streaming Quantile Estimation via Elastic Compactors
by: Gribelyuk, Elena, et al.
Published: (2024)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
by: Jiang, Cheng, et al.
Published: (2026)

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

Testing frequency distributions in a stream
by: Mathieu, Claire, et al.
Published: (2023)

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

$\ell_2/\ell_2$ Sparse Recovery via Weighted Hypergraph Peeling
by: Fischer, Nick, et al.
Published: (2025)

A $2\ell k$ Kernel for $\ell$-Component Order Connectivity
by: Kumar, Mithilesh, et al.
Published: (2016)

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

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

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

Permutation patterns in streams
by: Berendsohn, Benjamin Aram
Published: (2025)

On Finding $\ell$-th Smallest Perfect Matchings
by: Maalouly, Nicolas El, et al.
Published: (2025)

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

Engineering Semi-streaming DFS algorithms
by: Bhagavan, Kancharla Nikhilesh, et al.
Published: (2024)

Algorithms and Hardness Results for the $(k,\ell)$-Cover Problem
by: Madani, Amirali, et al.
Published: (2025)

Faster Approximate Fixed Points of $\ell_\infty$-Contractions
by: Feodorov, Andrei, et al.
Published: (2026)

Near-Optimal Constructive Bounds for $\ell_2$ Prefix Discrepancy and Steinitz Problems via Affine Spectral Independence
by: Dutta, Kunal, et al.
Published: (2026)

Local Gibbs sampling beyond local uniformity
by: Liu, Hongyang, et al.
Published: (2025)

Stable coresets: Unleashing the power of uniform sampling
by: Carmel, Amir, et al.
Published: (2025)

SimiSketch: Efficiently Estimating Similarity of streaming Multisets
by: Dong, Fenghao, et al.
Published: (2024)

Faster Semi-streaming Matchings via Alternating Trees
by: Mitrović, Slobodan, et al.
Published: (2024)

Optimal detection of dissipation in Lindbladian dynamics
by: Cai, Yiyi
Published: (2026)

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

Downstream: efficient cross-platform algorithms for fixed-capacity stream downsampling
by: Yang, Connor, et al.
Published: (2025)

Efficient stream-based Max-Min diversification with minimal failure rate
by: Kalogeratos, Argyris, et al.
Published: (2020)