Skip to content (access key 's')
Logo of Technion
Logo of CS Department


Theory Seminar: Network Coding Gaps for Completion Time of Multiple Unicasts
event speaker icon
David Wajc (CMU)
event date icon
Wednesday, 5.6.2019, 12:30
event location icon
Taub 201
Arguably the most common network communication problem is multiple-unicasts: Distinct packets at different nodes in a network need to be delivered to a destination specific to each packet, as fast as possible.

The famous multiple-unicast conjecture posits that, for this natural problem, there is no performance gap between routing and network coding, at least in terms of throughput. We study the same network coding gap, but in terms of completion time.

While throughput corresponds to the completion time for asymptotically-large transmissions, we look at completion times of multiple unicasts for arbitrary amounts of data. We develop nearly-matching upper and lower bounds for the network coding gap for this natural problem. In particular, we prove that the network coding gap for the completion time of k unicasts is at most polylogarithmic in k, and there exist instances of k unicasts for which this coding gap is polylogarithmic in k.

This talk is based on joint work with Bernhard Haeupler and Goran Zuzic.
[Back to the index of events]