AF: Large: Collaborative Research: Random Processes and Randomized Algorithms

AF：大型：协作研究：随机过程和随机算法

• 批准号: 0910415
• 负责人: Daniel Stefankovic
• 金额: $ 30万
• 依托单位: University of Rochester
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0910415&HistoricalAwards=false
• 关键词: AF; Large; Collaborative; Research; Random

Randomness has emerged as a core concept and tool in computation. From modeling phenomena to efficient algorithms to proof techniques, the applications of randomness are ubiquitous and powerful. Notable examples include: construction of important combinatorial objects such as expanders, rigorously establishing phase transitions in physical models, finding polynomial-time algorithms for fundamental sampling problems and approximating #P-hard counting problems, designing probabilistically checkable proofs (PCP's) and establishing the hardness of approximation, and discovering simpler and often faster algorithms for a variety of computational problems. In the course of these tremendous developments, several general-purpose techniques have emerged, and random sampling has become a fundamental, universal tool across sciences, engineering and computation. This project brings together leading researchers in randomized algorithms to solve hard problems in random sampling, to identify techniques, and to develop new analytical tools. The applications come from a range of fields, including complexity, physics, biology, operations research and mathematics. The most general and widely-studied technique for sampling is simulating a Markov chain by taking a random walk on a suitable state space. The Markov Chain method and its application to sampling, counting and integration, broadly known as the Markov Chain Monte Carlo (MCMC) method, is a central theme of the project. Intellectual Merit. The project focuses on applications of randomized algorithms and random sampling to rigorously address problems across several disciplines. Within computer science these topics include: massive data sets, where sampling is critical both for finding low-dimensional representations and clustering; routing networks, where sampling has many applications from monitoring and path allocation to optimization; machine learning; and property testing. Recent interactions between computer science and other scientic disciplines have led to many new rigorous applications of sampling, as well as new insights in how to design and analyze efficient algorithms with performance guarantees; for instance, phase transitions in the underlying physical models can cause local Markov chains to be inefficient. The project explores deeper connections between physics and random sampling, including conjectured correlations between reconstruction problems and thresholds for the efficiency of local algorithms. Many related problems arise in biology, such as phylogenetic tree reconstruction and analysis of complex biological networks. In nanotechology, models of self-assembly are simple Markov chains. In mathematics, the techniques used in the analysis of sampling algorithms in general and Markov chains in particular have drawn heavily on probability theory, both discrete and continuous. Broader Impact. The college of computing at Georgia Tech is home to the new Algorithms and Randomness Center (ARC) with many faculty and students sharing this expertise. The project's activities include designing a summer school for graduate students in randomized algorithms and designing a course for training students from diverse backgrounds and hosting workshops focusing on both theoretical and applied aspects of randomized algorithms. Participation of women and under-represented groups in all of these activities will be encouraged, and the workshops will include tutorials to increase accessibility. These coordinated efforts in education and research will solidify the impact of ARC and make it a premier center for algorithms, randomness and complexity.

随机性已成为计算的核心概念和工具。从建模现象到高效算法再到证明技术，随机性的应用无处不在且强大。值得注意的例子包括：构建重要的组合对象（例如扩展器）、在物理模型中严格建立相变、寻找基本采样问题的多项式时间算法和近似#P-hard计数问题、设计概率可检查证明（PCP）并建立硬度近似，并为各种计算问题发现更简单且通常更快的算法。在这些巨大发展的过程中，出现了几种通用技术，随机采样已成为科学、工程和计算领域的基本通用工具。该项目汇集了随机算法方面的领先研究人员，以解决随机抽样中的难题、确定技术并开发新的分析工具。这些应用程序来自多个领域，包括复杂性、物理、生物学、运筹学和数学。最普遍和广泛研究的采样技术是通过在合适的状态空间上进行随机游走来模拟马尔可夫链。马尔可夫链方法及其在采样、计数和积分中的应用，广泛称为马尔可夫链蒙特卡罗 (MCMC) 方法，是该项目的中心主题。智力优点。该项目侧重于随机算法和随机抽样的应用，以严格解决跨多个学科的问题。在计算机科学中，这些主题包括：海量数据集，其中采样对于查找低维表示和聚类都至关重要；路由网络，其中采样具有从监控、路径分配到优化的许多应用；机器学习；和性能测试。最近计算机科学和其他科学学科之间的相互作用带来了许多新的严格的采样应用，以及如何设计和分析具有性能保证的高效算法的新见解；例如，底层物理模型中的相变可能导致局部马尔可夫链效率低下。该项目探索了物理学和随机采样之间更深层的联系，包括重建问题和局部算法效率阈值之间的推测相关性。生物学中出现了许多相关问题，例如系统发育树重建和复杂生物网络的分析。在纳米技术中，自组装模型是简单的马尔可夫链。在数学中，一般采样算法和特别是马尔可夫链分析中使用的技术很大程度上依赖于概率论，包括离散的和连续的。更广泛的影响。佐治亚理工学院的计算机学院是新的算法和随机中心 (ARC) 的所在地，许多教职员工和学生都在分享这方面的专业知识。该项目的活动包括为随机算法研究生设计一所暑期学校，设计一门培训来自不同背景的学生的课程，并举办重点关注随机算法理论和应用方面的研讨会。将鼓励妇女和代表性不足的群体参与所有这些活动，研讨会将包括增加可及性的教程。这些教育和研究领域的协调努力将巩固 ARC 的影响力，使其成为算法、随机性和复杂性的首要中心。