Applications of Artihmetic Combinatorics in Computer Science

算术组合在计算机科学中的应用

• 批准号: 0729137
• 负责人: Luca Trevisan
• 金额: $ 33.8万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2010-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0729137&HistoricalAwards=false
• 关键词: Applications; Artihmetic; Combinatorics; 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.

算术组合学的最新进展得益于分析，千古理论，组合学和图理论的方法的收敛。这种新机械在长期以来的开放问题上取得了惊人的进步，例如关于素数中任意长时间算术进展的绿色陶器定理。这项研究是对这种新技术对理论计算机科学的应用的系统探索。分析性，图形理论和组合技术的某些技术已经在理论计算机科学中有许多应用，例如，诸如下线时间算法的设计，包括随机性提取器的构建，以及可证明的概率的设计。这项研究探讨了此类技术的新应用，以及厄基奇理论技术的应用。这项研究主要涉及从算术组合学到计算机科学的“技术转移”：在算术组合学和理论计算机科学家工作的纯数学家之间的合作增加将对这两个领域都有益，并且可能会超越理论计算机科学。