Applications of Artihmetic Combinatorics in Computer Science

算术组合学的最新进展得益于分析、遍历理论、组合学和图论方法的融合。这种新的机制导致了长期悬而未决的问题的惊人进展，例如关于素数中任意长算术级数的格林-陶定理。本研究系统地探索了这些新技术在理论计算机科学中的应用，其中一些分析、图论和组合技术已经在理论计算机科学中得到了大量的应用，如次线性时间算法的设计、随机性提取器的构造和概率可检验证明的设计等。本研究探讨了这些技术的新应用，以及遍历理论技术的应用。这项研究主要关注从算术组合学到计算机科学的“技术转移”：然而，算术组合学领域的纯数学家和理论计算机科学家之间加强合作将对这两个领域都有利，并且可能会产生积极的影响超越理论计算机科学。

Recent progress in arithmetic combinatorics has benefited from a convergence of methods from analysis, ergodic theory, combinatorics, and graph theory. This new machinery has led to spectacular progress on long-standing open questions, such as the Green-Tao theorem on arbitrarily long arithmetic progressions in the primes. This research is a systematic exploration of applications of such new techniques to theoretical computer science.Some of the analytic, graph-theoretic and combinatorial techniques have already had a number of applications to theoretical computer science, in such diverse areas as the design of sub-linear time algorithms, the construction of randomness extractors and the design of probabilistically checkable proofs. This research explores new applications of such techniques, as well as applications of the ergodic-theoretic techniques. This research is primarily concerned with a "technology transfer" from arithmetic combinatorics to computer science: increased collaboration between pure mathematicians working in arithmetic combinatorics and theoretical computer scientists will, however, be beneficial to both fields, and is likely to have a positive impact beyond theoretical computer science.