5 papers
The Multiple Unicast Conjecture is False
Mark Braverman, Zhongtian He
The undirected multiple-unicast conjecture [LL04] asserts that network coding offers no throughput advantage over multicommodity flow. We refute this conjecture by constructing a d…
Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
Matija Bucić, Zhongtian He, Shang-En Huang +1
We design efficient deterministic algorithms for finding short edge-disjoint paths in expanders. Specifically, given an -vertex -edge expander of conductance and mini…
Undirected Multicast Network Coding Gaps via Locally Decodable Codes
Mark Braverman, Zhongtian He
The network coding problem asks whether data throughput in a network can be increased using coding (compared to treating bits as commodities in a flow). While it is well-known that…
Cactus Representation of Minimum Cuts: Derandomize and Speed up
Zhongtian He, Shang-En Huang, Thatchaphol Saranurak
Given an undirected weighted graph with vertices and edges, we give the first deterministic -time algorithm for constructing the cactus representation of \emph{…
Cactus Representations in Polylogarithmic Max-flow via Maximal Isolating Mincuts
Zhongtian He, Shang-En Huang, Thatchaphol Saranurak
A cactus representation of a graph, introduced by Dinitz et al. in 1976, is an edge sparsifier of size that exactly captures all global minimum cuts of the graph. It is a ce…