课题基金 / 基金详情

Applications of Artihmetic Combinatorics in Computer Science

Applications of Artihmetic Combinatorics in Computer Science
算术组合在计算机科学中的应用
批准号:
0729137
负责人:
Luca Trevisan
金额:
$33.8万
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2007
资助国家:
美国
项目状态:
已结题
起止时间:
2007-09-01 至 2010-08-31

项目摘要

项目成果

Luca Trevisan的其他基金

相似基金

相关文献

中文摘要
翻译
算术组合学的最新进展得益于分析学、遍历论、组合学和图论等方法的融合。这种新机制在长期存在的开放问题上取得了惊人的进展,比如关于质数的任意长等差数列的格林-陶定理。本研究是对这些新技术在理论计算机科学中的应用的系统探索。一些分析技术、图论技术和组合技术已经在理论计算机科学中有了大量的应用,在亚线性时间算法的设计、随机提取器的构造和概率可检验证明的设计等不同领域。本研究探索了这些技术的新应用,以及遍历理论技术的应用。这项研究主要关注从算术组合到计算机科学的“技术转移”:然而,在算术组合领域工作的纯粹数学家和理论计算机科学家之间增加的合作将对两个领域都有益,并且可能对理论计算机科学以外的领域产生积极影响。
英文摘要
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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
AF: Small: Spectral and SDP Techniques: Average-Case Analysis and Subexponential Algorithms
  • 批准号:
    1815434
  • 项目类别:
    Standard Grant
  • 资助金额:
    $50.0万
  • 财政年份:
    2018
  • 负责人:
    Luca Trevisan
  • 依托单位:
EAGER: New Graph and CSP Algorithms Based on Spectral and SDP Techniques
  • 批准号:
    1655215
  • 项目类别:
    Standard Grant
  • 资助金额:
    $10.0万
  • 财政年份:
    2016
  • 负责人:
    Luca Trevisan
  • 依托单位:
AF: Small: Graph Partitioning and Spectral Methods
  • 批准号:
    1540685
  • 项目类别:
    Standard Grant
  • 资助金额:
    $28.97万
  • 财政年份:
    2014
  • 负责人:
    Luca Trevisan
  • 依托单位:
AF: Small: Graph Partitioning and Spectral Methods
  • 批准号:
    1216642
  • 项目类别:
    Standard Grant
  • 资助金额:
    $40.0万
  • 财政年份:
    2012
  • 负责人:
    Luca Trevisan
  • 依托单位:
海外基金