Buchumschlag

A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Sawettamalya, Pachara, Yu, Huacheng
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Near-Optimal Relative Error Streaming Quantile Estimation via Elastic Compactors
von: Gribelyuk, Elena, et al.
Veröffentlicht: (2024)

Minimum $s$--$t$ Cuts with Fewer Cut Queries
von: Jiang, Yonggang, et al.
Veröffentlicht: (2025)

Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
von: Gribelyuk, Elena, et al.
Veröffentlicht: (2025)

Optimally detecting uniformly-distributed $\ell_2$ heavy hitters in data streams
von: Velusamy, Santhoshini, et al.
Veröffentlicht: (2025)

A Strong Separation for Adversarially Robust $\ell_0$ Estimation for Linear Sketches
von: Gribelyuk, Elena, et al.
Veröffentlicht: (2024)

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

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
von: Georgiadis, Loukas, et al.
Veröffentlicht: (2026)

Deterministic Lower Bounds for $k$-Edge Connectivity in the Distributed Sketching Model
von: Robinson, Peter, et al.
Veröffentlicht: (2025)

Optimal Static Dictionary with Worst-Case Constant Query Time
von: Hu, Yang, et al.
Veröffentlicht: (2024)

Static Retrieval Revisited: To Optimality and Beyond
von: Hu, Yang, et al.
Veröffentlicht: (2025)

Ghost Value Augmentation for $k$-Edge-Connectivity
von: Hershkowitz, D Ellis, et al.
Veröffentlicht: (2023)

Deterministic $k$-Median Clustering in Near-Optimal Time
von: Costa, Martín, et al.
Veröffentlicht: (2025)

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
von: Hoppenworth, Gary, et al.
Veröffentlicht: (2025)

Fast and Compact Sketch-Based Dynamic Connectivity
von: De Man, Quinten, et al.
Veröffentlicht: (2025)

Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity
von: Bhanja, Koustav, et al.
Veröffentlicht: (2025)

Fully Dynamic k-Means Coreset in Near-Optimal Update Time
von: la Tour, Max Dupré, et al.
Veröffentlicht: (2024)

Fully Dynamic $k$-Median with Near-Optimal Update Time and Recourse
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Elastic Sketch under Random Stationary Streams: Limiting Behavior and Near-Optimal Configuration
von: Mazziane, Younes Ben, et al.
Veröffentlicht: (2026)

Nearly Optimal Bounds for Sample-Based Testing and Learning of $k$-Monotone Functions
von: Black, Hadley
Veröffentlicht: (2023)

Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
von: Korhonen, Tuukka
Veröffentlicht: (2024)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2024)

Independence-Number Parameterized Space Complexity for Directed Connectivity Certificate
von: Chen, Ho-Lin, et al.
Veröffentlicht: (2026)

Adaptive Fully Dynamic $k$-Center Clustering with (Near-)Optimal Worst-Case Guarantees
von: Grilnberger, Mara, et al.
Veröffentlicht: (2026)

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
von: Blikstad, Joakim, et al.
Veröffentlicht: (2025)

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs
von: De Man, Quinten, et al.
Veröffentlicht: (2026)

Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults
von: Parter, Merav, et al.
Veröffentlicht: (2024)

9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity
von: Çivril, Ali
Veröffentlicht: (2024)

Adversarial Robustness on Insertion-Deletion Streams
von: Gribelyuk, Elena, et al.
Veröffentlicht: (2026)

Time-Optimal $k$-Server
von: Frei, Fabian, et al.
Veröffentlicht: (2025)

Simple Algorithms for Fully Dynamic Edge Connectivity
von: Kenneth-Mordoch, Yotam, et al.
Veröffentlicht: (2025)

Online Edge Coloring is (Nearly) as Easy as Offline
von: Blikstad, Joakim, et al.
Veröffentlicht: (2024)

Nearly Optimal List Labeling
von: Bender, Michael A., et al.
Veröffentlicht: (2024)

Connected k-Median with Disjoint and Non-disjoint Clusters
von: Eube, Jan, et al.
Veröffentlicht: (2025)

The Connected k-Vertex One-Center Problem on Graphs
von: Zhang, Jingru
Veröffentlicht: (2024)

A $2\ell k$ Kernel for $\ell$-Component Order Connectivity
von: Kumar, Mithilesh, et al.
Veröffentlicht: (2016)

Key Compression Limits for $k$-Minimum Value Sketches
von: Dickens, Charlie, et al.
Veröffentlicht: (2024)

Optimal $k$-Secretary with Logarithmic Memory
von: Qiao, Mingda, et al.
Veröffentlicht: (2025)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
von: Goranci, Gramoz, et al.
Veröffentlicht: (2023)

Two-Edge Connectivity via Pac-Man Gluing
von: Garg, Mohit, et al.
Veröffentlicht: (2024)