BARC talk by Zhongtian He

Tuesday, September 1, 2026, 14:00-15:00, Zhongtian He, PhD Student at Princeton University, USA, will be giving a BARC talk on "Undirected Multicast Network Coding Gaps via Locally Decodable Codes".

Abstract:
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 a network coding advantage exists in directed graphs, the situation in undirected graphs is much less understood -- in particular, despite significant effort, it is not even known whether network coding is helpful at all for unicast sessions.

In this paper they study the multi-source multicast network coding problem in {\em undirected} graphs. There are $k$ sources broadcasting each to a subset of nodes in a graph of size $n$. The corresponding combinatorial problem is a version of the  Steiner tree packing problem, and the network coding question asks whether the multicast coding rate exceeds the tree-packing rate. They give the first super-constant bound to this problem, demonstrating an example with a coding advantage of $\Omega(\log k)$. In terms of graph size, we obtain a lower bound of $2^{\tilde{\Omega}(\sqrt{\log \log n})}$. They also obtain an upper bound of $O(\log n)$ on the gap.

Their main technical contribution is a new reduction that converts locally decodable codes in the low-error regime into multicast coding instances. This gives rise to a new family of explicitly constructed graphs, which may have other applications.

Based on the joint work of Mark Braverman and Zhongtian He.

Bio:
Zhongtian He is a PhD student in the theory group at Princeton University, advised by Mark Braverman. Before this, Zhongtian graduated from Yao Class at Tsinghua University in 2022.

Host:
Mikkel Thorup