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

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

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.