2 papers
cs.DS2025
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 min…
cs.CC2025
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…