ITR Collaborative Research: Complexity-Theoretic Applications of Fourier Analysis

点击翻译按钮获取中文摘要

Fourier 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.