Details of Grant 

EPSRC Reference:	EP/G064679/1
Title:	Advances in Sublinear Algorithms
Principal Investigator:	Czumaj, Professor A
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department:	Computer Science
Organisation:	University of Warwick
Scheme:	Standard Research
Starts:	01 September 2009	Ends:	28 February 2013	Value (£):	296,846
EPSRC Research Topic Classifications:	Fundamentals of Computing Information & Knowledge Mgmt
EPSRC Industrial Sector Classifications:	No relevance to Underpinning Sectors
Related Grants:
Panel History:	Panel Date Panel Name Outcome 04 Mar 2009 ICT Prioritisation Panel (March 09) Announced
Summary on Grant Application Form
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.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk Summary Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:
Further Information:
Organisation Website:	http://www.warwick.ac.uk