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.

The research proposed in this project, while of fundamental and theoretical character has a clear potential to impact the area of algorithms, and with this it has a long term potential to impact many areas of modern technologies.
To cope with modern requirements of big data it is of critical importance to advance the foundational research in algorithms, especially for algorithms that use computational resources significantly less than the input size - sublinear algorithms. By developing new algorithmic techniques for the analysis of big graphs and making significant advances in the area of sublinear algorithms for graph problems, the project is addressing one of the central challenges of modern computing - of computations and algorithms with limited resources - and is advancing the area of algorithms whose importance for modern technologies has been distinctly emphasized in various venues.

Interaction with industry:
The area of the proposal-design and analysis of sublinear algorithms for big graphs and networks-is of significant interest in several industrial research laboratories in North America, e.g., Microsoft, Google, Yahoo, IBM. While many of most important ideas in the area of sublinear algorithms and their big data applications originated in academia, more recently we have seen an increasing number of algorithmic developments in big high-tech companies. The PI has direct contacts with many leading researchers from main research laboratories in North America and he plans to enhance the collaboration with leading research labs with the goal of making further scientific advances in the field and also streamlining the impact of this research.
A significant part of the interaction with industry, especially in the context of the UK industry, is planned to be facilitated through interdisciplinary research centers at the University of Warwick. The PI plans to be involved in knowledge transfer activities in Warwick Data Science Institute, Warwick Institute for the Science of Cities, and Maths for Real-World Systems CDT. These Warwick research and training centers have close links to industry in the areas related to the project and the findings of the project will enhance this interaction.
The PI plans also to actively contribute to the interdisciplinary activities in the recently established Alan Turing Institute for Data Science in London that should facilitate close interaction of researchers in big data with leading industry.

Dissemination:
The results will be disseminated by publications in high quality international journals and conferences, and all papers will be published in open access venues. The PI will also maintain a web page with main activities of the project.
Besides publishing, the PI will give presentations about the results of this project in leading industrial research laboratories. The PI plans to visit, make presentations, and discuss further knowledge transfer activities in Microsoft Research Labs, IBM Research Center, Yahoo Labs, Google Research, BT Labs, etc.
Further impact will be achieved through national and international conferences. The PI has organized in the past several international workshops in the areas related to this project and those have been very well attended by industrial participants. The PI plans to organize further 2-3 workshops on sublinear algorithms and their applications, possibly going beyond this topic to a more general study of foundations of big data. These events would bring together leading academics and industrial researchers, system architects working in this area. To achieve a greater impact of these activities, the PI requests from EPSRC funding to organize one of these events, where he will invite leading academics, industrial researchers, system architects, and practitioners to discuss the advances of the design of efficient (sublinear) algorithms for big data problems with the special focus on the challenges of incorporating these advances in industry.