Sublinear Algorithms for Big Graphs

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

A fundamental task in the study of large networks is to efficiently analyze their structural properties. For example, we may want to know if a network is well-connected, is well-clusterable, has many copies (instances) of some specific sub-structures, etc. Given that modern networks are large, often consisting of millions and billions of nodes (web graph, social networks, etc.), the task of analyzing their structure has become recently increasingly challenging, and the running-time efficiency of this task is becoming of critical importance. Indeed, being able to quickly analyze important features in the gigantic amount of information already is a key technology of a multi-billion dollar industry (see, e.g., Google, Yahoo, Facebook, etc.) and its significance will likely increase further in the near future. To efficiently manage and analyze large networks, in recent years we have seen a rise of the importance of sublinear time algorithms, that is, algorithms that use significantly less resources than the input size. Since sublinear algorithms can process only a small fraction of the input, they are not suitable for many applications, especially if exact solutions are sought; but recently we have seen a number of sublinear algorithms that compute approximate solutions for a variety of optimization and decision problems arising in such diverse areas as algebraic computations, networks, geometry, and computer graphics.To cope with these modern challenges of large networks, this proposal will exploit the expertise of the PI in the area of randomized algorithms to develop new algorithmic techniques for the analysis of big graphs by making significant advances in the area of sublinear algorithms for combinatorial problems. The central goal is to push forward the barriers of our knowledge in the area of sublinear-time algorithms for graph problems by enlarging the class of problems for which sublinear-time are known and by characterizing problems for which sublinear-time algorithms are impossible to exist. The main technical goal is to develop algorithmic technology for the analysis of large graphs in the context of two central models: property testing algorithms and sublinear-time approximation algorithms. We plan also to apply the techniques developed to further models related to sublinear algorithms: data streaming, dynamic and online algorithms. Our objective is to attack grand challenges in the area of sublinear algorithms and we aim to make major advances. The focus of this project is on fundamental research in this area, aiming at advances in the area of theoretical aspects of the design and analysis of algorithms.