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.