ITR Collaborative Research: Complexity-Theoretic Applications of Fourier Analysis

更多的分析出现在许多著名的理论计算机科学的基石上。它在扩展图的构造和去随机化、复杂性下界、概率可检验证明系统、量子计算、分布式计算的下界以及计算机代数的传统应用中发挥着重要的作用。这些应用中的大多数涉及熟悉的交换傅里叶分析框架。提出的项目集合了一个多学科的研究团队，应用非阿贝尔(即非交换)傅立叶分析的美丽工具，在非阿贝利群最近变得非常重要的两个领域研究开放问题：并行计算的下界和量子算法。该程序还进一步开发了有限-阿贝尔群上离散傅立叶变换的有效算法。本项目专注于开发工具来分离复杂类Acc^0和Nc^1，以证明存在自然的(多项式时间可计算的)问题，在Acc^0意义下根本不能并行化。该项目应用了一系列新的工具来分离这些电路类别，使用非Abelan傅立叶分析来限制它们的计算能力。这些工具也适用于有限群上的方程求解问题，以及基于非阿贝尔群的新的概率可检验证明系统的发展。此外，该项目还应用非理想傅里叶分析，对图的同构的量子傅里叶变换的标准下界进行了改进，并研究了量子蒙特卡罗算法。最后，该项目专注于对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.