Harmonic Analysis on the Hamming Cube

汉明立方的调和分析

• 批准号: 2152346
• 负责人: Paata Ivanisvili
• 金额: $ 11.62万
• 依托单位: University of California-Irvine
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-07-01 至 2022-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2152346&HistoricalAwards=false
• 关键词: Harmonic; Analysis; Hamming; Cube

Many complex structures that arise in nature are perceived globally as continuous objects, although at the microscopic level they emerge from certain laws that appear to be discrete. What the relation is between the discrete and continuous "worlds", how one impacts the other, and what laws they obey are the fundamental questions that the PI intends to investigate. This project focuses on the Hamming cube, the simplest discrete object that consists of binary strings of given length and that can encode any complex information. As the complexity of the information increases, the lengths of the encoded strings increase exponentially. The goal of the project is to develop mathematics on the Hamming cube that would allow us to encode the structures of the continuous world into the discrete world, and vice versa. The new techniques developed could have surprising applications in complexity theory as well as classical and quantum algorithms. Many of these problems are accessible to students and this project aims to continue the PI's work with undergraduate and graduate students in this area. This project will consider a series of problems in the Gauss space and, most importantly, in its discrete counterpart, the Hamming cube. Unlike the classical case of the unit circle, many fundamental questions of Fourier analytic type are still open for the Hamming cube due to its unique discrete geometric structure. The first and main direction of the proposal is to resolve Weissler's conjecture, an old open problem in complex hypercontractivity theory on the Boolean cube that gives necessary and sufficient conditions for boundedness of the Hermite operator with complex time. Weissler's conjecture has important implications in several areas of mathematics including combinatorics, computer science, probability, isoperimetry, and approximation theory. The new techniques will be based on developing "two-point" inequalities. The second direction of this research is to develop methods of harmonic analysis to find good estimates on the norms of various linear operators acting on a class of functions on the Hamming cube whose Fourier spectra belong to given prescribed sets. The basic examples include Bernstein-Markov type inequalities and their reverse forms for functions on the Hamming cube that live on the low and high frequencies respectively. The third direction is to understand the universality phenomena of the Gaussian measure. In particular, the goal is to investigate uniqueness of the functional Ehrhard inequality, which is the sharp analog of Brunn-Minkowski inequality for the Gaussian measure. The analysis will be based on Monge-Ampere type partial differential equations and semigroup methods. The fourth direction is to develop the duality between martingale inequalities related to sharp dyadic square function estimates and the problems of isoperimetric type; that is, gradient estimates for functions on the Hamming cube. Our methods will use heat envelopes, "four-point" inequalities, and "inf-sup" Legendre transform. The fifth direction aims to obtain sharp forms of the classical triangle inequalities in the Lp spaces using the theory of developable surfaces and minimal concave functions.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.

自然界中出现的许多复杂结构在整体上被视为连续的物体，尽管在微观层面上它们是从某些看似离散的定律中出现的。离散和连续的“世界”之间的关系是什么，一个如何影响另一个，以及它们遵循什么规律是PI打算调查的基本问题。这个项目的重点是汉明立方体，最简单的离散对象，由给定长度的二进制字符串组成，可以编码任何复杂的信息。随着信息复杂性的增加，编码字符串的长度呈指数增长。该项目的目标是开发海明立方体上的数学，使我们能够将连续世界的结构编码到离散世界中，反之亦然。开发的新技术可能在复杂性理论以及经典和量子算法中有令人惊讶的应用。这些问题中的许多是学生可以接触到的，这个项目的目的是继续PI在这一领域的本科生和研究生的工作。这个项目将考虑高斯空间中的一系列问题，最重要的是，在其离散的对应物，汉明立方体。与单位圆的经典情况不同，由于汉明立方体独特的离散几何结构，许多傅立叶分析类型的基本问题仍然是开放的。该提案的第一个和主要方向是解决Weissler猜想，这是布尔立方体上的复超压缩理论中的一个古老的开放问题，它给出了Hermite算子有界性的充分必要条件。韦斯勒猜想在数学的几个领域有重要的意义，包括组合数学、计算机科学、概率论、等周学和近似理论。新技术将基于发展“两点”不等式。本研究的第二个方向是开发调和分析的方法，找到良好的估计的各种线性算子的规范作用于一类功能的汉明立方体的傅立叶谱属于给定的规定的集合。基本的例子包括Bernstein-Markov型不等式和它们的反向形式的功能上的汉明立方体，生活在低和高频率分别。第三个方向是理解高斯测度的普适性现象。特别地，我们的目标是研究泛函Ehrhard不等式的唯一性，它是Brunn-Minkowski不等式对于高斯测度的尖锐模拟。分析将基于Monge-Ampere型偏微分方程和半群方法。第四个方向是发展与尖锐的并元平方函数估计有关的鞅不等式和等周型问题之间的对偶性;即Hamming立方体上函数的梯度估计。我们的方法将使用热包络，“四点”不等式和“inf-sup”勒让德变换。第五个方向的目标是利用可展曲面和最小凹函数理论获得Lp空间中经典三角不等式的精确形式。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估而被认为值得支持。

项目成果

Learning low-degree functions from a logarithmic number of random queries

从对数数量的随机查询中学习低次函数

• DOI: 10.1145/3519935.3519981
• 发表时间: 2022
• 期刊: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Eskenazis, Alexandros;Ivanisvili, Paata
• 通讯作者: Ivanisvili, Paata

Hypercontractivity on the unit circle for ultraspherical measures: linear case

超球形测量单位圆上的超收缩性：线性情况

• DOI: 10.4171/rmi/1305
• 发表时间: 2022
• 期刊: Revista Matemática Iberoamericana
• 作者: Ivanisvili, Paata;Lindenberger, Alexander;Müller, Paul F.;Schmuckenschläger, Michael
• 通讯作者: Schmuckenschläger, Michael