AF: Medium: New Directions in Coding Theory and Pseudorandomness

点击翻译按钮获取中文摘要

The probabilistic method is a powerful tool to establish the existenceof diverse objects of importance in several applications. For example,Shannon's famous theorem asserts that a random codebook can be usedfor reliably transmitting information at optimal rates on a noisychannel. It is well known that a random graph is typically "Ramsey"and has no large clique or independent set, and a random sparse graphis very likely to be an expander with excellent connectivity. Yet, inapplications it is important to explicitly construct such an objectwith a certified guarantee of the desired property. Obtaining suchconstructions of comparable strength to what is guaranteed by theprobabilistic method is typically much harder and often unknown.Pseudorandomness is a broad area that deals with efficientlygenerating objects that exhibit the desirable properties of"random-like" objects despite being constructed either explicitly orwith limited randomness. Such pseudorandom constructions are importantin the study of error-correcting codes, complexity theory,combinatorics, cryptography, and high-dimensional geometry. Researchin recent years has addressed some of these challenges and led topowerful constructions of error-correcting codes, expander graphs,randomness extractors, Ramsey graphs, compressed sensing matrices,etc. Despite the seemingly different definitions and motivations forthe study of these objects, much of this progress was based oninsights uncovering intimate connections between them, leading to arich theory with a common pool of broadly useful techniques.This progress notwithstanding, explicit constructions with optimalparameters typically remain open, and the area is full of exciting newdirections motivated by emerging applications. This project willinvolve a comprehensive collection of interconnected researchactivities focusing on the theory of error-correcting codes andpseudorandomness. The directions pursued will include strengtheningthe existing connections between various pseudorandom constructs anddiscovering new computational applications thereof, and investigatingthe pseudorandom properties of codes and related objects that haveimportant structural characteristics often needed in applications(such as linearity or sparsity). Topics in coding theory inspired bycomplexity theory such as list decoding and locally testable codes,and codes for poorly understood noise models such as deletion channelswill be studied. Another important goal of the project is to bridgethe gap between worst-case and probabilistic noise models via codesfor channels with natural computational restrictions.The research will use ideas from computer science in setting newdirections for research in coding theory as well as discovering newconstructions of codes and decoding algorithms, thereby enhancing theconnection between the computer science and information theorycommunities. The discovery of new coding schemes has potential directapplications in communication and storage of data. Many of thequestions to be addressed, therefore, have a natural practicalconnection alongside their fundamental theoretical appeal. On theeducation front, the project will engage several graduate students andprovide a stimulating research environment for them, and help with theplanned writing of a "goal-oriented" textbook on coding theory.