The DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
On the Index Coding Problem and Its Relation to Network Coding and Matroid Theory
Open accessAbstract
Theindex codingproblem has recently attracted a significant attention from the research community due to its theoretical significance and applications in wireless ad hoc networks. An instance of the index coding problem includes a sender that holds a set of information messagesX={x1,...,xk}and a set of receiversR. Each receiver(x,H)inRneeds to obtain a messagex Xand has priorside informationconsisting of a subsetHofX. The sender uses a noiseless communication channel to broadcast encoding of messages inXto all clients. The objective is to find an encoding scheme that minimizes the number of transmissions required to satisfy the demands of all the receivers. In this paper, we analyze the relation between the index coding problem, the more general network coding problem, and the problem of finding a linear representation of a matroid. In particular, we show that any instance of the network coding and matroid representation problems can be efficiently reduced to an instance of the index coding problem. Our reduction implies that many important properties of the network coding and matroid representation problems carry over to the index coding problem. Specifically, we show thatvector linear codesoutperform scalar linear index codes and that vector linear codes are insufficient for achieving the optimum number of transmissions.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Ahlswede, R., Cai, N., Li, S.-Y. R., & Yeung, R. W. (2000) · IEEE Transactions on Information Theory · doi:10.1109/18.850663 · Cited by 7,814
Li, S.-Y. R., Yeung, R. W., & Cai, N. (2003) · IEEE Transactions on Information Theory · doi:10.1109/tit.2002.807285 · Cited by 3,378
An algebraic approach to network coding
Koetter, R., & Medard, M. (2003) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2003.818197 · Cited by 2,356
XORs in the Air: Practical Wireless Network Coding
Katti, S., Rahul, H., Hu, W., Katabi, D., Medard, M., & Crowcroft, J. (2008) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2008.923722 · Cited by 2,252
Polynomial Time Algorithms for Multicast Network Code Construction
Jaggi, S., Sanders, P., Chou, P. A., Effros, M., Egner, S., Jain, K., & Tolhuizen, L. M. G. M. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.847712 · Cited by 940
Birk, Y., & Kol, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.874540 · Cited by 324
Fragouli, C., & Soljanin, E. (2006) · now publishers, Inc. eBooks · doi:10.1561/9781601980335 · Cited by 288
The zero-error side information problem and chromatic numbers (Corresp.)
Witsenhausen, H. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055607 · Cited by 187
Broadcasting with Side Information
Alon, N., Lubetzky, E., Stav, U., Weinstein, A., & Hassidim, A. (2008) · 2008 49th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.41 · Cited by 184
Inferring Local Homology from Sampled Stratified Spaces
Bendich, P. L., Cohen‐Steiner, D., Edelsbrunner, H., Harer, J., & Morozov, D. (2007) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2007.45 · Cited by 68
Cited by
FemtoCaching: Wireless Content Delivery Through Distributed Caching Helpers
Shanmugam, K., Golrezaei, N., Dimakis, A. G., Molisch, A. F., & Caire, G. (2013) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2281606 · Cited by 1,246
Private information retrieval with side information: The single server case
Kadhe, S., Garcia, B., Heidarzadeh, A., Rouayheb, S. E., & Sprintson, A. (2017) · 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2017.8262860 · Cited by 38
Self-citation
Metadata
- Authors
- El Rouayheb, S., Sprintson, A., & Georghiades, C.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2010-07
- Volume
- 56
- Issue
- 7
- Pages
- 3187-3195
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2171844485
- Cited by
- 293
- References
- 11
- FWCI
- 28.03
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: On the Index Coding Problem and Its Relation to Network Coding and Matroid Theory. https://app.cochat.ai/papers/10.1109/tit.2010.2048502
- The paper
- El Rouayheb, S., Sprintson, A., & Georghiades, C. (2010). On the Index Coding Problem and Its Relation to Network Coding and Matroid Theory. IEEE Transactions on Information Theory. https://doi.org/10.1109/tit.2010.2048502
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
