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

CIF：小：差异和能量优化中的编码理论方法及其应用

基本信息

批准号：
2104489
负责人：
Alexander Barg
金额：
$ 50万
依托单位：
University of Maryland, College Park
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-07-01 至 2024-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2104489&HistoricalAwards=false
关键词：
CIF Small Coding theoretic methods

项目摘要

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.

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