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.