AF: Medium: New Directions in Coding Theory and Pseudorandomness

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

The probabilistic method is a powerful tool to establish the existence of diverse objects of importance in several applications. For example, Shannon's famous theorem asserts that a random codebook can be used for reliably transmitting information at optimal rates on a noisy channel. It is well known that a random graph is typically "Ramsey" and has no large clique or independent set, and a random sparse graph is very likely to be an expander with excellent connectivity. Yet, in applications it is important to explicitly construct such an object with a certified guarantee of the desired property. Obtaining such constructions of comparable strength to what is guaranteed by the probabilistic method is typically much harder and often unknown. Pseudorandomness is a broad area that deals with efficiently generating objects that exhibit the desirable properties of "random-like" objects despite being constructed either explicitly or with limited randomness. Such pseudorandom constructions are important in the study of error-correcting codes, complexity theory, combinatorics, cryptography, and high-dimensional geometry. Research in recent years has addressed some of these challenges and led to powerful constructions of error-correcting codes, expander graphs, randomness extractors, Ramsey graphs, compressed sensing matrices, etc. Despite the seemingly different definitions and motivations for the study of these objects, much of this progress was based on insights uncovering intimate connections between them, leading to a rich theory with a common pool of broadly useful techniques. This progress notwithstanding, explicit constructions with optimal parameters typically remain open, and the area is full of exciting new directions motivated by emerging applications. This project will involve a comprehensive collection of interconnected research activities focusing on the theory of error-correcting codes and pseudorandomness. The directions pursued will include strengthening the existing connections between various pseudorandom constructs and discovering new computational applications thereof, and investigating the pseudorandom properties of codes and related objects that have important structural characteristics often needed in applications (such as linearity or sparsity). Topics in coding theory inspired by complexity theory such as list decoding and locally testable codes, and codes for poorly understood noise models such as deletion channels will be studied. Another important goal of the project is to bridge the gap between worst-case and probabilistic noise models via codes for channels with natural computational restrictions. The research will use ideas from computer science in setting new directions for research in coding theory as well as discovering new constructions of codes and decoding algorithms, thereby enhancing the connection between the computer science and information theory communities. The discovery of new coding schemes has potential direct applications in communication and storage of data. Many of the questions to be addressed, therefore, have a natural practical connection alongside their fundamental theoretical appeal. On the education front, the project will engage several graduate students and provide a stimulating research environment for them, and help with the planned writing of a "goal-oriented" textbook on coding theory.