CIF: Small: Index Coding and Matrix Factorizations

CIF：小：索引编码和矩阵分解

• 批准号: 1618689
• 负责人: Georgios-Alex Dimakis
• 金额: $ 44.91万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-07-01 至 2019-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1618689&HistoricalAwards=false
• 关键词: CIF; Small; Index; Coding; Matrix

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.

许多通信系统，内容输送系统和机器学习算法都依赖于使用具有某些结构约束的矩阵因化的算法。重要的理论和实际兴趣的特定类型的基质分解称为“索引编码”。该项目的研究集中在研究索引编码的基础和用于结构矩阵因素化算法的开发。除了开发理论基础之外，这项研究有望为无线网络中的缓存和设计分布式存储代码提供更好的算法。该项目还包括课程开发，学生培训和教程演示的计划。该研究计划的具体重点包括三个推力：1）开发新颖的算法和索引编码的界限，2）了解索引编码与分布式存储代码的连接与分布式存储代码的连接其他分配问题的其他分解问题，以及3）使用索引编码来获得界限和可获得可观的信息流量问题。初步工作表明，这对于多个单播可以进行，更可能是更广泛的。该项目还考虑了与半编程松弛和图理论的连接。