Applications of structural matroid theory to minor-closed classes of codes

编码理论是研究以一种可以容忍传输错误的方式发送信息的方法。它在现代世界的应用范围很广，从读取划痕光盘上的数据，到在行星之间广播信息。不同的用途需要不同的传输方法或编码；一种重要的类型是二进制线性代码，其中每个消息都被解释为0和1的字符串，并被编码成具有特殊形式的更长的0 - 1字符串（或码字）。代码有两个难以同时最大化的理想特性，一个是它的速率，它用来衡量信息传输的效率，另一个是它的最小距离，它用来衡量它对错误的容忍度。我建议使用数学领域中被称为矩阵理论的深刻的新思想来研究代码或代码类在这种意义上的表现的理论极限，以及计算机解码代码的速度。***矩阵是一个抽象的数学对象，可以被认为是多维几何空间中点的构型。一种特殊类型的矩阵是二进制矩阵，它对应于二进制线性码。二元拟阵的两个子类是图形拟阵和地理拟阵，它们的结构来源于节点和边的网络；上述三个类都具有小闭类的理想特性。一个丰富的理论已经发展出来，它描述了二进制拟阵的小闭类的结构，从而也描述了二进制码的结构。特别是，虽然几乎所有的二进制码既不是图形的也不是图形的，但Geelen， Gerards和Whittle最近的一个开创性结果表明，在二进制码的每一个小闭子类中，几乎所有的成员都“接近”是图形的或图形的。*****后一个结果在编码理论中具有巨大的含义；粗略地说，任何已知对图形/图形代码为真的属性都应该更广泛地应用于小闭类。其中一个属性是最大似然解码阈值，这是一种衡量代码在仍然有效执行的情况下可以容忍的错误率的精确度量。最近，我与S. van Zwam一起确定了图形码的阈值，并建议将其扩展到所有二进制线性码的小闭类。另一个属性涉及解码码字的算法问题；众所周知，对于图形/图形代码，解码可以由计算机有效地执行，但对于二进制代码，解码是“NP-hard”；我建议使用矩阵结构理论来准确地理解产生这种分歧的有效解码的理论障碍是什么。***本研究将对我们理解信息传递的理论能力和极限做出重大贡献，并将加强编码理论和结构矩阵理论领域之间尚未开发的联系。* * * * *

Coding theory is the study of methods of sending information in a way that is tolerant of transmission errors. Its varied applications in the modern world range from reading data from a scratched disc, to broadcasting messages between planets. Different transmission methods, or codes, are required for different uses; one important type is a binary linear code, in which each message is interpreted as strings of zeroes and ones, and is encoded into a longer zero-one string (or codeword) with a special form. Two desirable properties of a code, difficult to maximize simultaneously, are its rate, a measure of how efficiently it transmits information, and its minimum distance, a measure of its tolerance to errors. I propose to use deep new ideas in an area of mathematics known as matroid theory to study theoretical limits on how well a code or class of codes can perform in this sense, as well as how rapidly codes can be decoded by computers.***A matroid is an abstract mathematical object that can be thought of as a configuration of points in multidimensional geometric space. A special type of matroid is a binary matroid, which corresponds to a binary linear code. Two subclasses of the binary matroids are the graphic and cographic matroids, which are matroids whose structure arises from a network of nodes and edges; all three of these mentioned classes have the desirable property of being minor-closed. A rich theory has developed that describes the structure of minor- closed classes of binary matroids, and consequently of binary codes. In particular, though nearly all binary codes are neither graphic nor cographic, a recent seminal result of Geelen, Gerards and Whittle shows that in every minor-closed subclass of binary codes, almost all the members are 'close' to being graphic or cographic.*****This latter result has huge implications in coding theory; roughly, any property that is known to be true for the graphic/cographic codes should apply more widely to minor-closed classes. One such property is the maximum-likelihood decoding threshold, a measure of exactly what error rate a code can tolerate while still performing effectively. With S. van Zwam, I recently determined this threshold for the graphic codes, and propose to extend it to all minor-closed classes of binary linear codes. Another property concerns the algorithmic problem of decoding codewords; for graphic/cographic codes it is known that decoding can be performed efficiently by a computer, but for binary codes it is known that decoding is 'NP-hard'; I propose to use matroid structure theory to understand precisely what the theoretical barrier is to efficient decoding that creates this divide. ***This research should have a significant contribution on our understanding of the theoretical capability and limits of information transmission, and will also strengthen the mostly untapped link between the fields of coding theory and structural matroid theory. *** **