Theoretical foundation of sublinear-time algorithms

许多科学领域目前正在经历一场戏剧性的变革：随着数据收集技术的快速进步，分子生物学家现在可以测量细胞中每个基因的表达水平；物理学家现在可以记录亚原子粒子碰撞的细节；天文学家现在可以获得宇宙最远端的详细图片；等等。现在可以收集的丰富数据集提供了许多令人兴奋的科学机会，但它们也带来了重大的新的计算挑战。次线性时间算法是帮助我们应对这些挑战的强大工具之一。次线性时间算法是一种算法，它只检查其输入的一小部分，并执行一些渐近小于输入大小的计算步骤，然后产生其输出。本提案中描述的研究旨在为这些算法的开发和分析提供坚实的理论基础。这将通过开发新的算法技术来设计次线性时间算法，开发新的数学工具来分析这些算法并确定它们的局限性，以及与理论计算机科学的其他领域建立新的联系。

Many areas of science are currently undergoing a dramatic transformation: with rapid advances in data collection technologies, molecular biologists can now measure the level of expression of every gene in a cell; physicists can now record the details of collisions of subatomic particles; astronomers can now obtain detailed pictures of the farthest reaches of the universe; etc. The rich datasets that can now be collected offer many exciting scientific opportunities, but they also introduce significant new computational challenges. Sublinear-time algorithms are one of the powerful tools that will help us meet these challenges. A sublinear-time algorithm is an algorithm that produces its output after inspecting only a tiny fraction of its input and executing a number of computational steps that is asymptotically smaller than the size of the input. The research described in this proposal aims to provide a solid theoretical foundation for the development and the analysis of these algorithms. This will be done by developing new algorithmic techniques for designing sublinear-time algorithms, new mathematical tools to analyze these algorithms and establish their limitations, and new connections to other areas of theoretical computer science.