CAREER: Discrete Structures and Orthogonal Systems

职业：离散结构和正交系统

• 批准号: 2152401
• 负责人: Paata Ivanisvili
• 金额: $ 40万
• 依托单位: University of California-Irvine
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-07-01 至 2025-08-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2152401&HistoricalAwards=false
• 关键词: CAREER; Discrete; Structures; Orthogonal; Systems

How much can quantum algorithms outperform classical algorithms? This open question has been recently formulated as a mathematical problem that has challenged the mathematical community but has yet to be solved. The question is related to another one: what is the most "efficient" way to encode and transmit given information? For example, a) one can try to minimize the number of symbols used in encoding the information, or b) one can maintain "certain structures" (say by repeating some "pattern") in encoded messages in order to avoid loss of information, provided that a couple of errors can be made during its transmission. The goal of this project is to investigate what the best way is to approximate given information or a given signal using only zeros and ones. The principal investigator will involve undergraduate and graduate students in research projects described in the proposal. The PI will organize a yearly summer school in analysis and probability for graduate students. This will be a good opportunity for PhD students to participate in research discussions with leading experts and to learn about emerging areas in mathematics. The question of quantum algorithms described above can be formulated as an explicit Fourier–analytic question on the boolean cube. On a technical level the proposal focuses on hypercontractivity, i.e., boundedness of a semigroup between normed spaces, its holomorphic extensions to complex domains, applications in moment comparison estimates, Markov—Bernstein type inequalities (for polynomials living on low and high frequencies), discrete approximation theory, and complexity of classical and quantum algorithms. One of the important examples involves the Hamming cube, equipped with a product measure. This project focuses on dimension independent estimates and proposes a program, a series of fundamental questions together with steps towards the resolution of these questions (heat flow arguments, martingale techniques, conformal maps, and probabilistic arguments), necessary for advancing and developing Fourier analysis on the Boolean cube.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.

量子算法的表现能优于经典算法多少？这个开放的问题最近被提出为数学问题，该问题挑战了数学社区，但尚未解决。这个问题与另一个问题有关：编码和传输给定信息的最“有效”的方法是什么？例如，a）可以尝试最大程度地减少编码信息编码的符号的数量，或者b）可以在编码消息中维护“某些结构”（例如，通过重复一些“模式”）维护，以避免丢失信息，前提是在传输过程中可以犯一些错误。该项目的目的是研究仅使用零和一个的最佳方法来近似给定信息或给定信号。首席研究人员将使本科生和研究生参与提案中描述的研究项目。 PI将组织一项年度暑期学校，以分析和研究生的可能性。学生。对于博士生来说，这将是一个很好的机会，可以与领先的专家参与研究讨论，并了解数学领域的新兴领域。上述量子算法的问题可以作为布尔立方体上的显式傅立叶 - 分析问题。 On a technical level the proposal focuses on hypercontractivity, i.e., boundedness of a semigroup between normed spaces, its holomorphic extensions to complex domains, applications in moment comparison estimates, Markov—Bernstein type inequalities (for polynomials living on low and high frequencies), discrete approximation theory, and complexity of classical and quantum algorithms.重要的例子之一是配备了产品测量的锤子立方体。该项目的重点是独立估计和提出一个计划，一系列基本问题，以及迈向解决这些问题的步骤（热流争论，玛格尔技术，结构图和概率论据），对于涉及BOOL CUBE的概述，通过评估NSF的规定依据，这是对BROOL COUBE的依据，这是必不可少的，这是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