Advances in Sublinear Algorithms

随着ICT技术的重要性和计算能力的稳步增加，ICT行业和计算机科学界广泛认识到，需要新的计算技术来有效地处理海量数据集。从计算的角度来看，现代处理海量数据集的方法需要使用次线性算法，即使用比输入大小小得多的资源(时间和空间)的算法。构建次线性时间算法似乎是一项不可能的任务，因为它假设一个人只能读取输入的一小部分。然而，近年来，我们看到了在图论、几何、代数计算和计算机图形学等不同领域中出现的用于组合和优化问题的次线性时间算法的发展。这个建议的主要目的是利用PI在随机算法和次线性算法领域的尖端专业知识，通过在组合问题的次线性算法领域取得进展，开发用于分析海量数据集的新算法技术。在这个项目中，我们打算在我们对次线性时间算法的理解上取得进展，扩大次线性时间已知的问题的类别，以及表征不可能存在次线性时间算法的问题。该建议的主要目标是在两个中心模型：次线性时间近似算法和属性测试算法的背景下，开发用于分析海量数据集的算法技术。我们的主要关注点是图问题，但也会考虑一些相关的组合问题。

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.