65 citations · 195 across the 64 of their papers we have counts for
6 papers · 1 filter
Streaming and Communication Complexity of Load-Balancing via Matching Contractors
Sepehr Assadi, Aaron Bernstein, Zachary Langley +2
In the load-balancing problem, we have an -vertex bipartite graph between a set of clients and servers. The goal is to find an assignment of all clients to the ser…
Vizing's Theorem in Near-Linear Time
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya +3
Vizing's theorem states that any -vertex -edge graph of maximum degree can be edge colored using at most different colors [Vizing, 1964]. Vizing's original proof i…
Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
Sepehr Assadi, Soheil Behnezhad, Christian Konrad +2
A semi-streaming algorithm in dynamic graph streams processes any -vertex graph by making one or multiple passes over a stream of insertions and deletions to edges of the graph…
Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs
Sepehr Assadi, Sanjeev Khanna, Peter Kiss
In a very recent breakthrough, Behnezhad and Ghafari [FOCS'24] developed a novel fully dynamic randomized algorithm for maintaining a -approximation of maximum matching with…
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
Sepehr Assadi, Prantar Ghosh, Bruno Loff +2
The following question arises naturally in the study of graph streaming algorithms: "Is there any graph problem which is "not too hard", in that it can be solved efficiently with t…
Faster Vizing and Near-Vizing Edge Coloring Algorithms
Sepehr Assadi
Vizing's celebrated theorem states that every simple graph with maximum degree admits a edge coloring which can be found in time on -vertex -edge g…