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的影响力，并使其成为算法、随机性和复杂性的首要中心。