ITR Collaborative Research: Complexity-Theoretic Applications of Fourier Analysis

University Of New Mexico, Albuquerque NM

Investigators

Abstract

Fourier analysis appears in many of the celebrated cornerstones of theoretical computer science. It plays essential roles in expander graph construction and derandomization, complexity lower bounds, probabilistically checkable proof systems, quantum computing, lower bounds for distributed computation, and traditional applications to computer algebra. The majority of these applications involve the familiar framework of commutative Fourier analysis. The proposed project brings together a multidisciplinary research team to apply the beautiful tools of non-Abelian (that is, noncommutative) Fourier analysis to investigate open questions in two areas where non-Abelian groups have recently become very important: lower bounds for parallel computation and quantum algorithms. The program also further develops efficient algorithms for the discrete Fourier transform over finite non-Abelian groups. This project focuses on developing tools for separating the complexity classes ACC^0 and NC^1, in order to demonstrate that there are natural (polynomial-time computable) problems which simply cannot be parallelized in the sense of ACC^0. The project applies a new family of tools for separating such circuit classes, using non-Abelian Fourier analysis to bound their computational power. These tools apply also to the problem of solving equations over finite groups, and the development of new probabilistically checkable proof systems based on non-Abelian groups. In addition, the project applies non-Abelian Fourier analysis to develop improved lower bounds on the standard Quantum Fourier Transform approach to Graph Isomorphism and study quantum Monte Carlo algorithms. Finally, the project focuses on adaptations of Bratelli diagrams and quivers to develop classical and quantum algorithms for the non-Abelian Fourier transform itself.