Higher-order fourier analysis and applications

著者

• Hatami, Hamed
• Hatami, Pooya
• Lovett, Shachar

書誌事項

Higher-order fourier analysis and applications

Hamed Hatami, Pooya Hatami, Shachar Lovett

（Foundations and trends in theoretical computer science, 13:4）

now Publishers, c2019

• : pbk

注記

Includes bibliographical references(p. 211-219)

内容説明・目次

内容説明

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.

目次

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

「Nielsen BookData」 より

詳細情報

• NII書誌ID(NCID): BC10314364
• ISBN:
  • 9781680835922
• 出版国コード: us
• タイトル言語コード: eng
• 本文言語コード: eng
• 出版地: Hanover, MA
• ページ数/冊数: 219 p.
• 大きさ: 24 cm
• 親書誌ID:
  • BA81053856