Local Algorithms for Random Networks: Power, Limitations and Applications

点击翻译按钮获取中文摘要

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.