ITR Collaborative Research: Complexity-Theoretic Applications of Fourier Analysis

乌里叶分析出现在许多著名的理论计算机科学基石中。它在扩展图构造和非随机化、复杂性下界、概率可检验证明系统、量子计算、分布式计算的下界以及计算机代数的传统应用中发挥着重要作用。这些应用中的大多数都涉及到我们熟悉的交换傅里叶分析框架。提议的项目汇集了一个多学科研究团队，应用非阿贝尔（即非交换）傅立叶分析的美丽工具来研究两个领域的开放问题，其中非阿贝尔群最近变得非常重要：并行计算的下界和量子算法。该程序还进一步开发了有限-阿贝尔群上离散傅里叶变换的有效算法。本项目侧重于开发用于分离复杂性类ACC^0和NC^1的工具，以证明存在自然（多项式时间可计算）问题，这些问题根本无法在ACC^0的意义上并行化。该项目应用了一系列新的工具来分离这些电路类，使用非阿贝尔傅立叶分析来限制它们的计算能力。这些工具也适用于在有限群上求解方程的问题，以及基于非阿贝尔群的新的概率可检验证明系统的发展。此外，该项目应用非阿贝尔傅立叶分析来开发改进的下界的标准量子傅立叶变换方法的图同构和研究量子蒙特卡罗算法。最后，该项目侧重于Bratelli图和颤振的适应性，以开发非阿贝尔傅里叶变换本身的经典和量子算法。

ourier analysis appears in many of the celebrated cornerstones oftheoretical computer science. It plays essential roles in expandergraph construction and derandomization, complexity lower bounds,probabilistically checkable proof systems, quantum computing, lowerbounds for distributed computation, and traditional applications tocomputer algebra. The majority of these applications involve thefamiliar framework of commutative Fourier analysis. The proposedproject brings together a multidisciplinary research team to apply thebeautiful tools of non-Abelian (that is, noncommutative) Fourieranalysis to investigate open questions in two areas where non-Abeliangroups have recently become very important: lower bounds for parallelcomputation and quantum algorithms. The program also further developsefficient algorithms for the discrete Fourier transform over finitenon-Abelian groups.This project focuses on developing tools for separating the complexityclasses ACC^0 and NC^1, in order to demonstrate that there are natural(polynomial-time computable) problems which simply cannot beparallelized in the sense of ACC^0. The project applies a new familyof tools for separating such circuit classes, using non-AbelianFourier analysis to bound their computational power. These tools applyalso to the problem of solving equations over finite groups, and thedevelopment of new probabilistically checkable proof systems based onnon-Abelian groups. In addition, the project applies non-AbelianFourier analysis to develop improved lower bounds on the standardQuantum Fourier Transform approach to Graph Isomorphism and studyquantum Monte Carlo algorithms. Finally, the project focuses onadaptations of Bratelli diagrams and quivers to develop classical andquantum algorithms for the non-Abelian Fourier transform itself.