Coding-theoretic methods in discrepancy and energy optimization, with applications

Faculty

Alexander Barg

Funding Agency

National Science Foundation

Year

2021

Descriptions

Collections of sequences of zeros and ones formed of n bits, called codes, are used for representing data to be stored in computer memory or transmitted over an optical cable. In many applications in communications, statistics, and computer science it is beneficial to choose a code that is in some ways uniformly distributed over the set of all the possible binary sequences. These applications have led researchers to define a large group of problems in applied mathematics both on the theory side and in the domain of data processing procedures.

This project relies on ideas drawn from recent developments in computer science as well as certain classical methods in applied mathematics, and it aims at new characterizations and applications of uniformly distributed sets of binary sequences. Barg will investigate uniformly distributed codes and their construction, evaluate their properties, look at a group of related geometric problems, and identify their uses in applied problems of algorithm design, computer vision, and economical representation of data.

The theory of uniform distributions has seen ongoing development through most of the last century, motivated primarily by problems of numerical integration of multivariable functions. In the context of point sets on the surface of the sphere in n dimensions, approximation to the uniform distribution is quantified by the quadratic discrepancy of the point set, measured as the average number of points of the set in a region of the surface of the sphere. Spherical point sets with small quadratic discrepancy approach uniformly distributed collections of points on the sphere. This project is devoted to an extension of this theory to binary codes that approximate the uniform distribution on the Hamming space.

Barg recently suggested ways of advancing the theory of such codes, including Fourier analysis on the Boolean cube, the theory of positive-definite kernels, linear programming, and other tools from coding theory. Applications of this work include estimating the error probability of decoding, derandomization of algorithms, and some variants of the compressed sensing problem.

This is a $500K National Science Foundation Communication and Information Foundations grant.