Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

Network Coding Gaps for Completion Times of Multiple

Davidd Wajc (Stanford)

Date & time: Wednesday, 07 October 2020 at 11:00AM - 12:00PM

Abstract: We study network coding gaps for the problem of makespan minimization of multiple unicasts. In this problem, distinct packets at different nodes in a network need to be delivered to a destination specific to each packet, as fast as possible. The \emph{network coding gap} specifies how much coding packets together in a network can help compared to the more natural approach of routing. 
While makespan minimization using routing has been intensely studied for the multiple unicasts problem, no bounds on network coding gaps for this problem are known. We develop new techniques which allow us to upper bound the network coding gap for the makespan of \(k\) unicasts, proving this gap is at most polylogarithmic in \(k\). Complementing this result, we show there exist instances of \(k\) unicasts for which this coding gap is polylogarithmic in \(k\). Our results also hold for average completion time, and more generally any \(\ell_p\) norm of completion times.

Based on joint work with Bernhard Haeupler and Goran Zuzic, to appear in FOCS'2020.

Mailing List

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.