All reports by Author Zhijun Zhang:

__
TR23-197
| 7th December 2023
__

Sepehr Assadi, Gillat Kol, Zhijun Zhang#### Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams

__
TR22-179
| 16th December 2022
__

Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang#### Round-vs-Resilience Tradeoffs for Binary Feedback Channels

__
TR22-136
| 21st September 2022
__

Sepehr Assadi, Gillat Kol, Zhijun Zhang#### Rounds vs Communication Tradeoffs for Maximal Independent Sets

__
TR22-129
| 15th September 2022
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang#### Binary Codes with Resilience Beyond 1/4 via Interaction

Sepehr Assadi, Gillat Kol, Zhijun Zhang

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 >>>

Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang

In a celebrated result from the $60$'s, Berlekamp showed that feedback can be used to increase the maximum fraction of adversarial noise that can be tolerated by binary error correcting codes from $1/4$ to $1/3$. However, his result relies on the assumption that feedback is "continuous", i.e., after every utilization ... more >>>

Sepehr Assadi, Gillat Kol, Zhijun Zhang

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 >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang

In the reliable transmission problem, a sender, Alice, wishes to transmit a bit-string x to a remote receiver, Bob, over a binary channel with adversarial noise. The solution to this problem is to encode x using an error correcting code. As it is long known that the distance of binary ... more >>>