Cover Image

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Assadi, Sepehr, Khanna, Sanjeev, Kiss, Peter
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
by: Behnezhad, Soheil, et al.
Published: (2024)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
by: Assadi, Sepehr, et al.
Published: (2025)

A note on Ordered Ruzsa-Szemerédi graphs
by: Pratt, Kevin
Published: (2025)

An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs using Fast Matrix Multiplication
by: Assadi, Sepehr, et al.
Published: (2025)

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
by: Assadi, Sepehr, et al.
Published: (2026)

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
by: Chuzhoy, Julia, et al.
Published: (2026)

Faster Vizing and Near-Vizing Edge Coloring Algorithms
by: Assadi, Sepehr
Published: (2024)

A Simple $(1-ε)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
by: Assadi, Sepehr
Published: (2023)

Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette Sparsification
by: Assadi, Sepehr, et al.
Published: (2025)

Streaming Maximal Matching with Bounded Deletions
by: Khanna, Sanjeev, et al.
Published: (2025)

The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits
by: Assadi, Sepehr, et al.
Published: (2023)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
by: Assadi, Sepehr, et al.
Published: (2024)

Streaming and Communication Complexity of Load-Balancing via Matching Contractors
by: Assadi, Sepehr, et al.
Published: (2024)

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

Better Bounds for Semi-Streaming Single-Source Shortest Paths
by: Assadi, Sepehr, et al.
Published: (2025)

Maximum Bipartite Matching in $n^{2+o(1)}$ Time via a Combinatorial Algorithm
by: Chuzhoy, Julia, et al.
Published: (2024)

Coloring Graphs with Few Colors in the Streaming Model
by: Assadi, Sepehr, et al.
Published: (2025)

Covering Approximate Shortest Paths with DAGs
by: Assadi, Sepehr, et al.
Published: (2025)

Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
by: Goranci, Gramoz, et al.
Published: (2025)

Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $Δ$-Coloring
by: Assadi, Sepehr, et al.
Published: (2022)

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
by: Bhattacharya, Sayan, et al.
Published: (2023)

Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

Fully Dynamic Algorithms for Chamfer Distance
by: Goranci, Gramoz, et al.
Published: (2025)

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
by: Khanna, Sanjeev, et al.
Published: (2024)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
by: Assadi, Sepehr, et al.
Published: (2024)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
by: Bhattacharya, Sayan, et al.
Published: (2023)

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
by: Khanna, Sanjeev, et al.
Published: (2025)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
by: Bernstein, Aaron, et al.
Published: (2025)

An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths
by: Khanna, Sanjeev, et al.
Published: (2026)

An algorithmic Polynomial Freiman-Ruzsa theorem
by: Castro-Silva, Davi, et al.
Published: (2026)

Vizing's Theorem in Near-Linear Time
by: Assadi, Sepehr, et al.
Published: (2024)

Vizing's Theorem in Deterministic Almost-Linear Time
by: Assadi, Sepehr, et al.
Published: (2025)

Distributed Triangle Detection is Hard in Few Rounds
by: Assadi, Sepehr, et al.
Published: (2025)

Fully-Dynamic Submodular Cover with Bounded Recourse
by: Gupta, Anupam, et al.
Published: (2020)

A Theory of Spectral CSP Sparsification
by: Khanna, Sanjeev, et al.
Published: (2025)

Query Complexity of the Metric Steiner Tree Problem
by: Chen, Yu, et al.
Published: (2022)

On the Parallel Complexity of Finding a Matroid Basis
by: Khanna, Sanjeev, et al.
Published: (2025)

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
by: Khanna, Sanjeev, et al.
Published: (2026)

Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
by: Bernstein, Aaron, et al.
Published: (2025)

On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication
by: Liu, Yang P.
Published: (2024)