CIF: Small: Structured-Network Coding: Fundamental Limits via Submodular Function Optimization

分布式和云存储是新兴技术，它改变了当今个人和企业数据的管理方式。本项目提出网络编码作为建模工具，研究分布式和云存储系统的高效设计和运行。该项目的主要目的是开发数学工具，建立在香农熵的子模块化基础上，以捕获此类工程网络编码问题的结构，从而产生强大且易于计算的网络编码边界。本项目的两个重点是：1)子集熵不等式的组合表征；2)广播网络的广义割集界。我们提出的网络编码研究与传统观点有很大的不同，传统观点认为网络编码是纯数学问题的集合。这种偏差使我们能够从组合学和信息论中关注适当的工具，并从工程直觉中汲取力量。该项目的理论发展和工程成果预计将影响未来几年网络编码领域的发展。拟议的研究项目与我们在培养本科生和研究生、扩大妇女和非裔美国人在工程领域的参与以及通过与高中生接触来鼓励未来的科学家等方面的持续努力密切相关。

Distributed and cloud storage are emerging technologies that transform the way personal and enterprise data are managed today. This project proposes network coding as a modeling tool to study efficient design and operation of distributed and cloud storage systems. The principal aim of this project is to develop mathematical tools that build upon the submodularity of Shannon entropy to capture the structure of such engineering network coding problems, yielding strong yet easy-to-compute network coding bounds. Two specific focuses of this project are: 1) combinatorial characterization of subset entropy inequalities; and 2) generalized cut-set bounds for broadcast networks.Our proposed study of network coding represents a significant deviation from the traditional view, where network coding is seen as a collection of pure mathematical problems. This deviation allows us to focus on the appropriate tools from combinatorics and information theory and draw strength from engineering intuitions. Both the theoretical development and the engineering results from this project are expected to impact how the field of network coding evolves over the next few years. The proposed research programs are hand-in-hand with our continuing efforts in training undergraduate and graduate students, broadening the participation of women and African Americans in engineering, and encouraging future scientists through outreach to high-school students.