CIF: Small: Index Coding and Matrix Factorizations

点击翻译按钮获取中文摘要

Many communication systems, content delivery systems, and machine learning algorithms rely on algorithms that use matrix factorizations with some structure constraints. A specific type of matrix factorization of significant theoretical and practical interest is called "Index Coding". The research in this project is centered around studying the foundations of index coding and the development of algorithms for structured matrix factorizations. Beyond the development of theoretical foundations, this research is expected to lead to better algorithms for caching in wireless networks and for designing distributed storage codes. The project also includes plans for curriculum development, student training, and tutorial presentations.The specific focus of this research program consists of three thrusts: 1) Developing novel algorithms and bounds for index coding, 2) Understanding the connections of index coding with distributed storage codes other factorization problems and 3) Using index coding to obtain bounds and achievable schemes for information flow problems. Preliminary work indicates that this is possible for multiple unicasts and more possibly more generally. Connections with semidefinite programming relaxations and graph theory are also considered in this project.