Connecting multiple-unicast and network error correction: Reduction and unachievability

Wentao Huang; Michael Langberg; Joerg Kliewer

doi:10.1109/ISIT.2015.7282477

Connecting multiple-unicast and network error correction: Reduction and unachievability

Wentao Huang, Michael Langberg, Joerg Kliewer

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

4 Scopus citations

Abstract

We show that solving a multiple-unicast network coding problem can be reduced to solving a single-unicast network error correction problem, where an adversary may jam at most a single edge in the network. Specifically, we present an efficient reduction that maps a multiple-unicast network coding instance to a network error correction instance while preserving feasibility. The reduction holds for both the zero probability of error model and the vanishing probability of error model. Previous reductions are restricted to the zero-error case. As an application of the reduction, we present a constructive example showing that the single-unicast network error correction capacity may not be achievable, a result of separate interest.

Original language	English (US)
Title of host publication	Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	361-365
Number of pages	5
ISBN (Electronic)	9781467377041
DOIs	https://doi.org/10.1109/ISIT.2015.7282477
State	Published - Sep 28 2015
Externally published	Yes
Event	IEEE International Symposium on Information Theory, ISIT 2015 - Hong Kong, Hong Kong Duration: Jun 14 2015 → Jun 19 2015

Publication series

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

Other

Other	IEEE International Symposium on Information Theory, ISIT 2015
Country/Territory	Hong Kong
City	Hong Kong
Period	6/14/15 → 6/19/15

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2015.7282477

Cite this

Huang, W., Langberg, M., & Kliewer, J. (2015). Connecting multiple-unicast and network error correction: Reduction and unachievability. In Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015 (pp. 361-365). Article 7282477 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2015-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2015.7282477

@inproceedings{f420a94787ff42868030b578b0a9b2d1,

title = "Connecting multiple-unicast and network error correction: Reduction and unachievability",

abstract = "We show that solving a multiple-unicast network coding problem can be reduced to solving a single-unicast network error correction problem, where an adversary may jam at most a single edge in the network. Specifically, we present an efficient reduction that maps a multiple-unicast network coding instance to a network error correction instance while preserving feasibility. The reduction holds for both the zero probability of error model and the vanishing probability of error model. Previous reductions are restricted to the zero-error case. As an application of the reduction, we present a constructive example showing that the single-unicast network error correction capacity may not be achievable, a result of separate interest.",

author = "Wentao Huang and Michael Langberg and Joerg Kliewer",

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; IEEE International Symposium on Information Theory, ISIT 2015 ; Conference date: 14-06-2015 Through 19-06-2015",

year = "2015",

month = sep,

day = "28",

doi = "10.1109/ISIT.2015.7282477",

language = "English (US)",

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

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

pages = "361--365",

booktitle = "Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015",

address = "United States",

}

Huang, W, Langberg, M & Kliewer, J 2015, Connecting multiple-unicast and network error correction: Reduction and unachievability. in Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015., 7282477, IEEE International Symposium on Information Theory - Proceedings, vol. 2015-June, Institute of Electrical and Electronics Engineers Inc., pp. 361-365, IEEE International Symposium on Information Theory, ISIT 2015, Hong Kong, Hong Kong, 6/14/15. https://doi.org/10.1109/ISIT.2015.7282477

Connecting multiple-unicast and network error correction: Reduction and unachievability. / Huang, Wentao; Langberg, Michael; Kliewer, Joerg.
Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015. Institute of Electrical and Electronics Engineers Inc., 2015. p. 361-365 7282477 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2015-June).

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

TY - GEN

T1 - Connecting multiple-unicast and network error correction

T2 - IEEE International Symposium on Information Theory, ISIT 2015

AU - Huang, Wentao

AU - Langberg, Michael

AU - Kliewer, Joerg

PY - 2015/9/28

Y1 - 2015/9/28

N2 - We show that solving a multiple-unicast network coding problem can be reduced to solving a single-unicast network error correction problem, where an adversary may jam at most a single edge in the network. Specifically, we present an efficient reduction that maps a multiple-unicast network coding instance to a network error correction instance while preserving feasibility. The reduction holds for both the zero probability of error model and the vanishing probability of error model. Previous reductions are restricted to the zero-error case. As an application of the reduction, we present a constructive example showing that the single-unicast network error correction capacity may not be achievable, a result of separate interest.

AB - We show that solving a multiple-unicast network coding problem can be reduced to solving a single-unicast network error correction problem, where an adversary may jam at most a single edge in the network. Specifically, we present an efficient reduction that maps a multiple-unicast network coding instance to a network error correction instance while preserving feasibility. The reduction holds for both the zero probability of error model and the vanishing probability of error model. Previous reductions are restricted to the zero-error case. As an application of the reduction, we present a constructive example showing that the single-unicast network error correction capacity may not be achievable, a result of separate interest.

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

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

U2 - 10.1109/ISIT.2015.7282477

DO - 10.1109/ISIT.2015.7282477

M3 - Conference contribution

AN - SCOPUS:84969895411

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 361

EP - 365

BT - Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 14 June 2015 through 19 June 2015

ER -

Huang W, Langberg M, Kliewer J. Connecting multiple-unicast and network error correction: Reduction and unachievability. In Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015. Institute of Electrical and Electronics Engineers Inc. 2015. p. 361-365. 7282477. (IEEE International Symposium on Information Theory - Proceedings). doi: 10.1109/ISIT.2015.7282477

Connecting multiple-unicast and network error correction: Reduction and unachievability

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this