Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Sepehr Assadi:

TR23-197 | 7th December 2023
Sepehr Assadi, Gillat Kol, Zhijun Zhang

Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams

The seminal work of Ahn, Guha, and McGregor in 2012 introduced the graph sketching technique and used it to present the first streaming algorithms for various graph problems over dynamic streams with both insertions and deletions of edges. This includes algorithms for cut sparsification, spanners, matchings, and minimum spanning trees ... more >>>

TR22-136 | 21st September 2022
Sepehr Assadi, Gillat Kol, Zhijun Zhang

Rounds vs Communication Tradeoffs for Maximal Independent Sets

We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There are $n$ players corresponding to vertices of an undirected graph, and each player sees the edges incident on its vertex -- this way, each edge is known by both ... more >>>

ISSN 1433-8092 | Imprint