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.