Advances in Sublinear Algorithms

With the growing significance of ICT technologies and with the steady increase in computational power, the need for new, computational techniques to process efficiently massive datasets is widely acknowledged by the ICT industry and the Computer Science community. From the computational viewpoint, the modern approach to massive datasets requires the use of sublinear algorithms, that is, algorithms that use resources (time and space) significantly less than the input size. Constructing sublinear time algorithms may seem to be an impossible task since it assumes that one can read only a small fraction of the input. However, in recent years, we have seen developments of sublinear time algorithms for combinatorial and optimisation problems arising in such diverse areas as graph theory, geometry, algebraic computations, and computer graphics. The main objective of this proposal is exploit the cutting edge expertise of the PI in the area of randomised algorithms and sublinear algorithms to develop new algorithmic techniques for the analysis of massive datasets by making advances in the broadly understood area of sublinear algorithms for combinatorial problems.In this project, we intend to make a progress in our understanding of sublinear-time algorithms and enlarge the class of problems for which sublinear-time are known, as well as, to characterise problems for which sublinear-time algorithms are impossible to exist. The main objective of this proposal is to develop algorithmic technology for the analysis of massive data sets in the context of two central models: sublinear-time approximation algorithms and property testing algorithms. Our main focus is on graph problems, though also some related combinatorial problems will be considered.