Student: Carter McCall, Undergraduate Student in Mathematics and Computer Science, Drake University
Faculty Mentor: Dr. Christopher Porter
Kolmogorov Complexity and Error-Correcting Codes
Despite the many advances in the theory of error-correcting codes, many questions still remain about the existence of codes that balance both efficiency and reliability. In particular, it is not known whether the function that enumerates all pairs (R,d), where R is the transmission rate (efficiency) of a code C and d is the minimum Hamming distance (reliability) of codewords in C, can be approximated by an algorithm. If this function can be approximated by an algorithm, this could allow for the discovery of new error-correcting codes, which could increase the reliability and efficiency of data transmission.
Recently, progress has been made on solving the above problem using Kolmogorov complexity, which is a measure of the complexity of the description of an object. Kolmogorov complexity was used to show that the above function can be approximated as long as we equip the algorithm with additional information. The goal of this project is to determine the extent to which this solution can be modified to remove this additional information, and more generally, what leverage can Kolmogorov complexity provide in the search for new error-correcting codes.