ITR Collaborative Research: Complexity-Theoretic Applications of Fourier Analysis

ITR 合作研究：傅立叶分析的复杂性理论应用

• 批准号: 0220264
• 负责人: Alexander Russell
• 金额: $ 12.05万
• 依托单位: University of Connecticut
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-09-15 至 2005-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0220264&HistoricalAwards=false
• 关键词: ITR; Collaborative; Research; Complexity; Theoretic

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.

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