Skip to main content

Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All

Author(s): Braverman, Mark; Garg, Sumegha; Schvartzman, Ariel

To refer to this page use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBraverman, Mark-
dc.contributor.authorGarg, Sumegha-
dc.contributor.authorSchvartzman, Ariel-
dc.identifier.citationBraverman, Mark, Sumegha Garg, and Ariel Schvartzman. "Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All." 8th Innovations in Theoretical Computer Science Conference (ITCS) 67 (2017). doi:10.4230/LIPIcs.ITCS.2017.18en_US
dc.description.abstractWhile it is known that using network coding can significantly improve the throughput of directed networks, it is a notorious open problem whether coding yields any advantage over the multicommodity flow (MCF) rate in undirected networks. It was conjectured that the answer is no. In this paper we show that even a small advantage over MCF can be amplified to yield a near-maximum possible gap. We prove that any undirected network with k source-sink pairs that exhibits a (1+epsilon) gap between its MCF rate and its network coding rate can be used to construct a family of graphs G' whose gap is log(|G'|)^c for some constant c < 1. The resulting gap is close to the best currently known upper bound, log(|G'|), which follows from the connection between MCF and sparsest cuts. Our construction relies on a gap-amplifying graph tensor product that, given two graphs G1,G2 with small gaps, creates another graph G with a gap that is equal to the product of the previous two, at the cost of increasing the size of the graph. We iterate this process to obtain a gap of log(|G'|)^c from any initial gap.en_US
dc.format.extent18:1 - 18:18en_US
dc.relation.ispartof8th Innovations in Theoretical Computer Science Conference (ITCS 2017)en_US
dc.rightsFinal published version. This is an open access article.en_US
dc.titleCoding in Undirected Graphs Is Either Very Helpful or Not Helpful at Allen_US
dc.typeConference Articleen_US

Files in This Item:
File Description SizeFormat 
CodingUndirectedGraphsHelpfulOrNot.pdf823.71 kBAdobe PDFView/Download

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.