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

该项目研究由n个比特组成的0和1序列的性质。这种序列的集合称为代码，用于表示要存储在计算机存储器中或通过光缆传输的数据。在通信、统计和计算机科学的许多应用中，选择在所有可能的二进制序列的集合上以某种方式均匀分布的代码是有益的。这些应用使研究人员在理论和数据处理程序领域定义了一大组应用数学问题。本课题主要研究均匀分布码的构造、性质评价、一组相关的几何问题以及它们在算法设计、计算机视觉、数据经济表示等应用问题中的应用。该项目依赖于计算机科学的最新发展以及应用数学中的某些经典方法，旨在研究二进制序列的均匀分布集合的新特征和应用。均匀分布理论在上个世纪的大部分时间里一直在不断发展，主要是由于多变量函数的数值积分问题。在n维球表面上的点集的上下文中，通过点集的二次差来量化对均匀分布的逼近，该点集的平方差被测量为球面区域中该集的平均点数。球面点集的二次小偏差逼近球面上均匀分布的点集。本项目致力于将这一理论推广到接近汉明空间上均匀分布的二进制代码。研究人员在最近的工作中提出了推进这类码理论的方法，这些方法依赖于布尔立方体上的傅立叶分析、正定核理论、线性规划和其他来自编码理论的工具。这项工作的应用包括估计解码的错误概率、算法的去随机化以及压缩传感问题的一些变体。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The project studies properties of sequences of zeros and ones formed of n bits. Collections of such sequences, 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. The main topic of this project is investigation of uniformly distributed codes, including their construction, evaluation of the properties, a group of related geometric problems, as well and their uses in applied problems of algorithm design, computer vision, and economical representation of data. The 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.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. Ways of advancing the theory of such codes were suggested in recent works of the investigator, and they rely on 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 award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.