Grant: Discovery Grants Program - Individual
University of Waterloo
$31,000.00
Applications of structural matroid theory to minor-closed classes of codes
FY 2020-21
Summary
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.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2016-04131
Name nom
Nelson, Alexander
Department département
Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2020
Competition year année de concours
2016
Award amount
31000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2718
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Communication and information theory
Research subject fr
Théorie des télécommunications et de l'information
Installment
inst:5-6
Partie
2
Nb partie
6
Application title
Applications of structural matroid theory to minor-closed classes of codes
Keyword
NSERC
Application summary
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.