CAREER: Discrete Structures and Orthogonal Systems

量子算法能胜过经典算法多少？这个开放的问题最近被表述为一个数学问题，它挑战了数学界，但尚未得到解决。这个问题与另一个问题有关：对给定信息进行编码和传输的最“有效”方式是什么？例如，a)可以尽量减少信息编码中使用的符号数量，或者b)可以在编码信息中保持“特定结构”（例如通过重复某些“模式”），以避免信息丢失，前提是在传输过程中可能出现一些错误。这个项目的目标是研究只使用0和1来近似给定信息或给定信号的最佳方法。首席研究员将让本科生和研究生参与提案中描述的研究项目。PI将为研究生组织一年一度的分析和概率暑期学校。这将是一个很好的机会，博士生参与研究讨论与领先的专家和了解新兴领域的数学。上面描述的量子算法问题可以表述为布尔立方体上的显式傅立叶解析问题。在技术层面上，该建议着重于超收缩性，即在赋范空间之间的半群的有界性，它的全纯扩展到复域，在矩比较估计中的应用，Markov-Bernstein型不等式（对于生活在低频和高频上的多项式），离散逼近理论，以及经典和量子算法的复杂性。其中一个重要的例子涉及汉明立方体，它配备了一个产品度量。该项目关注维度独立估计，并提出了一个程序，一系列基本问题以及解决这些问题的步骤（热流参数，鞅技术，保角映射和概率参数），这是推进和发展布尔立方体的傅里叶分析所必需的。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.