Cover Image

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Assadi, Sepehr, Behnezhad, Soheil, Konrad, Christian, Naidu, Kheeran K., Sundaresan, Janani
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

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

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

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

Single-Pass Streaming CSPs via Two-Tier Sampling
by: Azarmehr, Amir, et al.
Published: (2026)

Streaming Complexity Separations for Dense and Sparse Graphs
by: Liu, Yang P., et al.
Published: (2026)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
by: Fei, Yumou, et al.
Published: (2025)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
by: Li, Qian, et al.
Published: (2025)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
by: Fei, Yumou, et al.
Published: (2025)

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

Neighborhood-Aware Graph Labeling Problem
by: Shahverdikondori, Mohammad, et al.
Published: (2026)

Approximating Maximum Matching Requires Almost Quadratic Time
by: Behnezhad, Soheil, et al.
Published: (2024)

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)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)

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

Unit Interval Selection in Random Order Streams
by: Alexandru, Cezar-Mihail, et al.
Published: (2026)

Half-Approximating Maximum Dicut in the Streaming Setting
by: Azarmehr, Amir, et al.
Published: (2025)

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs
by: Assadi, Sepehr, et al.
Published: (2024)

The Fine-Grained Complexity of Episode Matching
by: Bille, Philip, et al.
Published: (2021)

Semi-Streaming Algorithms for Graph Property Certification
by: Das, Avinandan, et al.
Published: (2025)

Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
by: Azarmehr, Amir, et al.
Published: (2024)

Matching and Edge Cover in Temporal Graphs
by: Cioni, Lapo, et al.
Published: (2025)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
by: Shih, Yu-Sheng, et al.
Published: (2026)

Parameterized Complexity of Vehicle Routing
by: Döring, Michelle, et al.
Published: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
by: Moroie, Gregory
Published: (2025)

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

A New Information Complexity Measure for Multi-pass Streaming with Applications
by: Braverman, Mark, et al.
Published: (2024)

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

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
by: Chudigiewitsch, Florian, et al.
Published: (2026)

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

The Query Complexity of Local Search in Rounds on General Graphs
by: Brânzei, Simina, et al.
Published: (2026)

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

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching
by: Dreier, Jan, et al.
Published: (2026)

On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting
by: Firbas, Alexander, et al.
Published: (2024)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
by: Focke, Jacob, et al.
Published: (2023)