源于分布式网络的离散模型与组合学方法

Discrete configurations and combinatorial methods originated from distributed network

近年来,分布式网络环境架构下的诸多新型信息科学问题为经典信息论和编码理论带来了新的挑战.这些问题的研究涉及多种离散模型,组合设计、图论、组合编码和极值组合学等组合学方法在其中发挥了至关重要的作用.本文选取网络编码、索引编码、编码缓存、分布式计算和隐私保护信息检索这5个源于分布式网络环境的信息科学前沿热点问题,简要介绍各问题研究进展,并着重介绍其中涉及的离散模型与组合学思想方法.同时,本文针对上述多个专题分别给出一些新结果.

In recent years, many new problems of information science originating from distributed networks have brought new challenges to the classical information theory and coding theory. The research of these problems involves many discrete configurations. Combinatorial methods such as combinatorial design theory, graph theory,combinatorial coding theory and extremal combinatorics have been playing an important role in the research of these problems. In this paper, we briefly survey the progress on five hot frontier topics originating from distributed networks, including network coding, index coding, coded caching, distributed computing, and private information retrieval. In particular, we emphasize the discrete configurations and combinatorial methods related to these topics. For some of the topics, we also provide a few new results.