Local Algorithms for Random Networks: Power, Limitations and Applications

该奖项的研究目标是系统地了解随机网络上组合优化问题的局部算法的性能和局限性。现代技术、通信和社交网络的规模使得许多计算工具和概念过于不切实际，无法满足当代的计算速度。针对这一挑战，近年来对网络计算模型的研究主要集中在局部算法范式上。现实生活中网络最常见的生成模型之一是随机图模型。因此，本文的研究重点是随机图的局部算法的性能和局限性。一个特别的重点是研究随机图上组合问题的所谓解空间几何及其对局部算法设计和分析的意义。现在已知，某些优化问题经历相变性质，称为破碎，描述为将可行解空间分裂成许多不连通的分量。构建在这个相变点之外执行的算法的许多尝试都没有成功。因此，破碎性被认为是超出相变点的局部算法不存在的主要原因。PI最近的一项工作证明了在这个相变点以外的一些优化问题不存在局部算法，从而首次建立了破碎相变性质与算法性能之间的直接联系。这项研究的重点是系统地研究相变特性和算法设计之间的这种迷人的联系。如果成功，这项研究的结果将在局部算法的性能和算法复杂性与随机网络的结构特性之间提供深层次的联系。研究议程真正是跨学科的，处于几个领域的十字路口。这些活动利用了各种学科的工具，包括算法理论、组合学和图论、应用概率和统计物理学，从而汇集了不同群体的想法。这项研究的结果将在各自领域的顶级期刊和会议上传播。将举办研究研讨会，向学生介绍网络上的算法和计算这一主题。

The research objective of this award is to develop systematic understanding of the performance and limitations of local algorithms for combinatorial optimization problems on random networks. The scale of modern technological, communication and social networks renders many computational tools and concepts too impractical to meet the contemporary computational speeds. In light of this challenge, the research on network computational models has recently focused on local algorithms paradigm. One of the most common generative models for real life networks is the random graph model. Thus the research focuses on the performance and limitations of local algorithms for random graphs. A particular focus is on studying the so-called solution space geometry of combinatorial problems on random graphs and its implications for the design and analysis of local algorithms. It is now known that certain optimization problems undergo a phase transition property, dubbed shattering, described as splitting of the space of feasible solutions into many disconnected components. Many attempts to construct algorithms which perform beyond this phase transition point did not succeed. Thus the shattering property is conjectured to be the main "culprit" for the non-existence of local algorithms beyond the phase transition point. A recent work of the PI establishes the non-existence of local algorithms for some optimization problems beyond this phase transition point, thus establishing for the first time the direct link between the shattering phase transition property and the performance of algorithms. The research focuses on the systematic study of this fascinating link between the phase transition property and the design of algorithms. If successful, the results of this research will provide a deep connection between the performance and algorithmic complexity of local algorithms and structural properties of random networks. The research agenda is truly interdisciplinary, lying at the crossroads of several fields. The activities draw on tools from a variety of disciplines, including the theory of algorithms, combinatorics and graph theory, applied probability and statistical physics, thus bringing together ideas from a diverse set of communities. The results of this research will be disseminated in top journals and conferences in the respective fields. Research seminars will be conducted to introduce students to the topic of algorithms and computations on networks.