Hamed Hatami, Pooya Hatami and Shachar Lovett (2019), "Higher-order Fourier Analysis and Applications", Foundations and Trends® in Theoretical Computer Science: Vol. 13: No. 4, pp 247-448. http://dx.doi.org/10.1561/0400000064

© 2019 H. Hatami, P. Hatami and S. Lovett

Download article
**In this article:**

1. Introduction

Part I. Low Degree Testing

2. Low Degree Testing

3. Low-degree Tests, the 99% Regime

4. Low-degree Tests, the 1% Regime

5. Gowers Norms, the Inverse Gowers Conjecture and its Failure

Part II. Higher Order Fourier Analysis

6. Nonclassical Polynomials, and the Inverse Gowers Theorem

7. Rank, Regularity, and Other Notions of Uniformity

8. Bias vs Low Rank in Large Fields

9. Decomposition Theorems

10. Homogeneous Nonclassical Polynomials

11. Complexity of Systems of Linear Forms

12. Deferred Technical Proofs

13. Algorithmic Regularity

Part III. Algebraic Property Testing

14. Algebraic Properties

15. One-Sided Algebraic Property Testing

16. Degree Structural Properties

17. Estimating the Distance from Algebraic Properties

Part IV. Open Problems

18. Open Problems

References

Fourier analysis has been extremely useful in many areas of mathematics. In the last several decades, it has been used extensively in theoretical computer science. Higher-order Fourier analysis is an extension of the classical Fourier analysis, where one allows to generalize the “linear phases” to higher degree polynomials. It has emerged from the seminal proof of Gowers of Szemerédi’s theorem with improved quantitative bounds, and has been developed since, chiefly by the number theory community. In parallel, it has found applications also in theoretical computer science, mostly in algebraic property testing, coding theory and complexity theory. The purpose of this book is to lay the foundations of higherorder Fourier analysis, aimed towards applications in theoretical computer science with a focus on algebraic property testing.

230 pp. $99.00

Buy book (pb)
230 pp. $140.00

Buy E-book (.pdf)
1. Introduction

Part I. Low Degree Testing

2. Low Degree Testing

3. Low-degree Tests, the 99% Regime

4. Low-degree Tests, the 1% Regime

5. Gowers Norms, the Inverse Gowers Conjecture and its Failure

Part II. Higher Order Fourier Analysis

6. Nonclassical Polynomials, and the Inverse Gowers Theorem

7. Rank, Regularity, and Other Notions of Uniformity

8. Bias vs Low Rank in Large Fields

9. Decomposition Theorems

10. Homogeneous Nonclassical Polynomials

11. Complexity of Systems of Linear Forms

12. Deferred Technical Proofs

13. Algorithmic Regularity

Part III. Algebraic Property Testing

14. Algebraic Properties

15. One-Sided Algebraic Property Testing

16. Degree Structural Properties

17. Estimating the Distance from Algebraic Properties

Part IV. Open Problems

18. Open Problems

References

*Higher-order Fourier Analysis and Applications* provides an introduction to the field of higher-order Fourier analysis with an emphasis on its applications to theoretical computer science. Higher-order Fourier analysis is an extension of the classical Fourier analysis. It has been developed by several mathematicians over the past few decades in order to study problems in an area of mathematics called additive combinatorics, which is primarily concerned with linear patterns such as arithmetic progressions in subsets of integers.

The monograph is divided into three parts: Part I discusses linearity testing and its generalization to higher degree polynomials. Part II present the fundamental results of the theory of higher-order Fourier analysis. Part III uses the tools developed in Part II to prove some general results about property testing for algebraic properties. It describes applications of the theory of higher-order Fourier analysis in theoretical computer science, and, to this end, presents the foundations of this theory through such applications; in particular to the area of property testing.