CIF: Small: Index Coding and Matrix Factorizations

许多通信系统、内容交付系统和机器学习算法依赖于使用具有某些结构约束的矩阵分解的算法。具有重要理论和实践意义的一种特定类型的矩阵因式分解被称为“索引编码”。本计画的研究主要集中在索引编码的基础与结构化矩阵分解演算法的发展。除了理论基础的发展，这项研究预计将导致更好的算法在无线网络中的缓存和设计分布式存储代码。该项目还包括课程开发计划，学生培训，和tutorial presentations.本研究计划的具体重点包括三个推力：1）开发新的算法和索引编码的界限，2）理解索引编码与分布式存储代码的连接其他因式分解问题和3）使用索引编码，以获得信息流问题的界限和可实现的方案。初步工作表明，这对于多个单播是可能的，并且更可能更普遍。半定规划松弛和图论的连接也被认为是在这个项目中。

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.