Cover Image

Fast and Compact Sketch-Based Dynamic Connectivity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	De Man, Quinten, Jafri, Qamber, Delayo, Daniel, West, Evan T., Bender, Michael A., Tench, David
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs
by: De Man, Quinten, et al.
Published: (2026)

The Case for External Graph Sketching
by: Bender, Michael A., et al.
Published: (2025)

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

UFO Trees: Practical and Provably-Efficient Parallel Batch-Dynamic Trees
by: De Man, Quinten, et al.
Published: (2026)

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

Towards Scalable and Practical Batch-Dynamic Connectivity
by: De Man, Quinten, et al.
Published: (2024)

Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance
by: Song, Zhao, et al.
Published: (2022)

Adaptive Quotient Filters
by: Wen, Richard, et al.
Published: (2024)

Fully-Dynamic Parallel Algorithms for Single-Linkage Clustering
by: De Man, Quinten, et al.
Published: (2025)

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

On Sketching Trimmed Statistics
by: Lin, Honghao, et al.
Published: (2025)

On Sketching Quadratic Forms
by: Andoni, Alexandr, et al.
Published: (2015)

Designing Compact ILPs via Fast Witness Verification
by: Włodarczyk, Michał
Published: (2025)

Almost Linear Size Edit Distance Sketch
by: Koucký, Michal, et al.
Published: (2024)

Approximation Algorithms for Steiner Connectivity Augmentation
by: Hathcock, Daniel, et al.
Published: (2023)

Average-Distortion Sketching
by: Bao, Yiqiao, et al.
Published: (2024)

LMQ-Sketch: Lagom Multi-Query Sketch for High-Rate Online Analytics
by: Hilgendorf, Martin, et al.
Published: (2025)

Multipass Linear Sketches for Geometric LP-Type Problems
by: Çekirge, N. Efe, et al.
Published: (2025)

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
by: Khanna, Sanjeev, et al.
Published: (2025)

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

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

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

Sketching Cuts in Graphs and Hypergraphs
by: Kogan, Dmitry, et al.
Published: (2014)

On Differential Privacy for Adaptively Solving Search Problems via Sketching
by: Feng, Shiyuan, et al.
Published: (2025)

Approximating Tensor Network Contraction with Sketches
by: Heddes, Mike, et al.
Published: (2026)

Optimal Non-Oblivious Open Addressing
by: Bender, Michael A., et al.
Published: (2025)

Tight Bounds for Classical Open Addressing
by: Bender, Michael A., 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)

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

Simple Algorithms for Fully Dynamic Edge Connectivity
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Dynamic Pricing Algorithms for Online Set Cover
by: Bender, Max, et al.
Published: (2024)

MagnifierSketch: Quantile Estimation Centered at One Point
by: Guo, Jiarui, et al.
Published: (2025)

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

Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs
by: Ahmadian, Sara, et al.
Published: (2024)

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

Fully Dynamic Strongly Connected Components in Planar Digraphs
by: Karczmarz, Adam, et al.
Published: (2024)

History-Independent Load Balancing
by: Bender, Michael A., et al.
Published: (2026)

A Dynamic Working Set Method for Compressed Sensing
by: Cheng, Siu-Wing, et al.
Published: (2025)

Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
by: Cohen, Edith, et al.
Published: (2025)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
by: Khanna, Sanjeev, et al.
Published: (2024)