ITR Collaborative Research: Complexity-Theoretic Applications of Fourier Analysis

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

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.