CIF: Small: New Approaches to the Design and Analysis of Graphical Models for Linear Codes and Secret Sharing Schemes

摘要：恐怖纠错编码使人们能够设计可靠的信息传输和存储系统，并被广泛用于通过网络发送数据包，在CD和闪存设备上写入数据，以及其他类似的现代通信手段。为保护错误而对信息进行编码的一种非常有效的方法是所谓的“迭代解码”，这种方法假设传输的每个二进制数字都是基于其可靠性和编码消息中精心选择的其他几个位的可靠性来恢复的。这种纠错方法是基于编码在平面上作为图的表示来分析的，在平面上，通过在若干轮中执行的迭代过程中在图的节点之间连续交换信息来进行错误恢复。本研究的主要目标之一是减少从通信介质中的错误中可靠地恢复传输所需的复杂性（轮数）。到目前为止，线性码的图形模型仅限于格子，即无循环图和只有一个循环的图（咬尾格子）。本文研究了带环连通图的编码实现复杂度和迭代译码算法，并从图的树分解中得到了复杂度估计。本研究的目标之一是为Reed-Muller和Reed-Solomon等知名码族寻找构建低复杂度代码实现的方法，并探索这些表示的最优性差距。在分析秘密共享方案和安全多方计算协议的访问结构时，还将探讨用于图模型研究的拟阵理论方法。

NSF Proposal 0916919 New approaches to the design and analysis of graphical models for linear codes and secret sharing schemesAbstractError-correcting coding enables one to design reliable systems of transmission and storage of information and is used universally for sending packets over the web, in writing data on CD's and flash memory devices, and other similar means of modern communication. A very efficient method of encoding information for error protection is the so-called "iterative decoding," which assumes that every binary digit of transmission is recovered based on its realiblity and the realibility of a few other, carefully selected bits of the encoded message. This method of error correction is analyzed based on the representation of the encoding as a graph in the plane in which recovery from errors proceeds by successive exchange of information between the nodes of the graph in an iterative procedure performed in a number of rounds. One of the main goals of this research is to reduce complexity (the number of rounds) needed for reliable recovery of the transmission from errors in the communication medium.Graphical models of linear codes have so far been restricted to trellises, i.e., cycle-free graphs, and graphs with exactly one cycle (tail-biting trellises). This research studies complexity of realization of codes and iterative decoding algorithms on connected graphs with cycles, deriving complexity estimates from the tree-decomposition of graphs. One of the goals of this research is to find methods of constructing low-complexity realizations of codes for such well-known code families as Reed-Muller and Reed-Solomon codes, and explore the optimality gap of these representations. Methods of matroid theory used in the study of graphical models will also be explored in the analysis of access structures of secret sharing schemes and secure multi-party computation protocols.