Advances in Sublinear Algorithms

Lead Research Organisation: University of Warwick
Department Name: Computer Science

Abstract

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.

Publications

10 25 50
publication icon
Lachish O (2009) Testing Periodicity in Algorithmica

publication icon
CZUMAJ A (2010) Testing Expansion in Bounded-Degree Graphs in Combinatorics, Probability and Computing

publication icon
Czumaj A (2014) Finding cycles and trees in sublinear time in Random Structures & Algorithms

publication icon
Adamaszek M (2010) Property Testing

publication icon
Czumaj A (2010) Property Testing

publication icon
Czumaj A (2010) Algorithms - ESA 2010

 
Description The project has made significant advances in the area of property testing and sublinear algorithms, as demonstrated by several influential publications in this area.

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 optimisation problems arising in such diverse areas as graph theory, geometry, algebraic computations, and computer graphics. The main objective of this proposal was to exploit the cutting edge expertise of the PI and his collaborators 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.

Specific scientific highlights of the project include a new testing algorithm for monotone continuous distributions on high-dimensional real cubes (SODA'10), constant-time bipartitness testing algorithms for arbitrary planar graphs (FOCS'11), characterization of testable properties in bounded-degree graphs (RSA 2014), and very fast approximation algorithms for facility location (including streaming algorithms).
Exploitation Route Property testing and sublinear algorithms provide a potentially interesting framework to design super-fast algorithms. The results in this area, including some of the results obtained in this project, demonstrated that some fundamental combinatorial problems can be solved very quickly. These ideas are frequently taken on by research laboratories, including leading research labs in Google, Yahoo, Microsoft, to transfer these findings into more applied products.
Sectors Digital/Communication/Information Technologies (including Software)