Linear network coding for two-unicast-Z networks: A commutative algebraic perspective and fundamental limits

Mohammad Fahim; Viveck R. Cadambe

doi:10.1109/ISIT.2017.8006714

Linear network coding for two-unicast-Z networks: A commutative algebraic perspective and fundamental limits

Mohammad Fahim, Viveck R. Cadambe

Electrical Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We consider a two-unicast-Z network over a directed acyclic graph of unit capacitated edges; the two-unicast-Z network is a special case of two-unicast networks where one of the destinations has apriori side information of the unwanted (interfering) message. In this paper, we settle open questions on the limits of network coding for two-unicast-Z networks by showing that the generalized network sharing bound is not tight, vector linear codes outperform scalar linear codes, and nonlinear codes outperform linear codes in general. We also develop a commutative algebraic approach to deriving linear network coding achievability results, and demonstrate our approach by providing an alternate proof to the previous result of Wang et. al. regarding feasibility of rate (1,1) in the network.

Original language	English (US)
Title of host publication	2017 IEEE International Symposium on Information Theory, ISIT 2017
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1177-1181
Number of pages	5
ISBN (Electronic)	9781509040964
DOIs	https://doi.org/10.1109/ISIT.2017.8006714
State	Published - Aug 9 2017
Event	2017 IEEE International Symposium on Information Theory, ISIT 2017 - Aachen, Germany Duration: Jun 25 2017 → Jun 30 2017

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
ISSN (Print)	2157-8095

Other

Other	2017 IEEE International Symposium on Information Theory, ISIT 2017
Country/Territory	Germany
City	Aachen
Period	6/25/17 → 6/30/17

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2017.8006714

Cite this

Fahim, M., & Cadambe, V. R. (2017). Linear network coding for two-unicast-Z networks: A commutative algebraic perspective and fundamental limits. In 2017 IEEE International Symposium on Information Theory, ISIT 2017 (pp. 1177-1181). Article 8006714 (IEEE International Symposium on Information Theory - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2017.8006714

@inproceedings{ca65cff1ca8d4a5899c92df3375d4866,

title = "Linear network coding for two-unicast-Z networks: A commutative algebraic perspective and fundamental limits",

abstract = "We consider a two-unicast-Z network over a directed acyclic graph of unit capacitated edges; the two-unicast-Z network is a special case of two-unicast networks where one of the destinations has apriori side information of the unwanted (interfering) message. In this paper, we settle open questions on the limits of network coding for two-unicast-Z networks by showing that the generalized network sharing bound is not tight, vector linear codes outperform scalar linear codes, and nonlinear codes outperform linear codes in general. We also develop a commutative algebraic approach to deriving linear network coding achievability results, and demonstrate our approach by providing an alternate proof to the previous result of Wang et. al. regarding feasibility of rate (1,1) in the network.",

author = "Mohammad Fahim and Cadambe, {Viveck R.}",

note = "Funding Information: This work is supported by NSF grant No. CCF 1464336. Publisher Copyright: {\textcopyright} 2017 IEEE.; 2017 IEEE International Symposium on Information Theory, ISIT 2017 ; Conference date: 25-06-2017 Through 30-06-2017",

year = "2017",

month = aug,

day = "9",

doi = "10.1109/ISIT.2017.8006714",

language = "English (US)",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1177--1181",

booktitle = "2017 IEEE International Symposium on Information Theory, ISIT 2017",

address = "United States",

}

Fahim, M & Cadambe, VR 2017, Linear network coding for two-unicast-Z networks: A commutative algebraic perspective and fundamental limits. in 2017 IEEE International Symposium on Information Theory, ISIT 2017., 8006714, IEEE International Symposium on Information Theory - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 1177-1181, 2017 IEEE International Symposium on Information Theory, ISIT 2017, Aachen, Germany, 6/25/17. https://doi.org/10.1109/ISIT.2017.8006714

Linear network coding for two-unicast-Z networks: A commutative algebraic perspective and fundamental limits. / Fahim, Mohammad; Cadambe, Viveck R.
2017 IEEE International Symposium on Information Theory, ISIT 2017. Institute of Electrical and Electronics Engineers Inc., 2017. p. 1177-1181 8006714 (IEEE International Symposium on Information Theory - Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Linear network coding for two-unicast-Z networks

T2 - 2017 IEEE International Symposium on Information Theory, ISIT 2017

AU - Fahim, Mohammad

AU - Cadambe, Viveck R.

PY - 2017/8/9

Y1 - 2017/8/9

N2 - We consider a two-unicast-Z network over a directed acyclic graph of unit capacitated edges; the two-unicast-Z network is a special case of two-unicast networks where one of the destinations has apriori side information of the unwanted (interfering) message. In this paper, we settle open questions on the limits of network coding for two-unicast-Z networks by showing that the generalized network sharing bound is not tight, vector linear codes outperform scalar linear codes, and nonlinear codes outperform linear codes in general. We also develop a commutative algebraic approach to deriving linear network coding achievability results, and demonstrate our approach by providing an alternate proof to the previous result of Wang et. al. regarding feasibility of rate (1,1) in the network.

AB - We consider a two-unicast-Z network over a directed acyclic graph of unit capacitated edges; the two-unicast-Z network is a special case of two-unicast networks where one of the destinations has apriori side information of the unwanted (interfering) message. In this paper, we settle open questions on the limits of network coding for two-unicast-Z networks by showing that the generalized network sharing bound is not tight, vector linear codes outperform scalar linear codes, and nonlinear codes outperform linear codes in general. We also develop a commutative algebraic approach to deriving linear network coding achievability results, and demonstrate our approach by providing an alternate proof to the previous result of Wang et. al. regarding feasibility of rate (1,1) in the network.

UR - http://www.scopus.com/inward/record.url?scp=85034088958&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85034088958&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2017.8006714

DO - 10.1109/ISIT.2017.8006714

M3 - Conference contribution

AN - SCOPUS:85034088958

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1177

EP - 1181

BT - 2017 IEEE International Symposium on Information Theory, ISIT 2017

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 25 June 2017 through 30 June 2017

ER -

Fahim M, Cadambe VR. Linear network coding for two-unicast-Z networks: A commutative algebraic perspective and fundamental limits. In 2017 IEEE International Symposium on Information Theory, ISIT 2017. Institute of Electrical and Electronics Engineers Inc. 2017. p. 1177-1181. 8006714. (IEEE International Symposium on Information Theory - Proceedings). doi: 10.1109/ISIT.2017.8006714

Linear network coding for two-unicast-Z networks: A commutative algebraic perspective and fundamental limits

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this