Research Perspectives - Tools for Visualisation of Portfolios
EPSRC logo

EPSRC Database


Source RCUK EPSRC Data

EP/G064679/1 - Advances in Sublinear Algorithms

Research Perspectives grant details from EPSRC portfolio

http://www.researchperspectives.org/gow.grants/grant_EPG0646791.png

Professor A Czumaj EP/G064679/1 - Advances in Sublinear Algorithms

Principal Investigator - Computer Science, University of Warwick

Scheme

Standard Research

Research Areas

Maths of Computing Maths of Computing

Start Date

09/2009

End Date

02/2013

Value

£296,846

Similar Grants

Automatic generation of similar EPSRC grants

Similar Topics

Topic similar to the description of this grant

Grant Description

Summary and Description of the grant

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.

Structured Data / Microdata


Grant Event Details:
Name: Advances in Sublinear Algorithms - EP/G064679/1
Start Date: 2009-09-01T00:00:00+00:00
End Date: 2013-02-28T00:00:00+00:00

Organization: University of Warwick

Description: 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 co ...