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

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

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.