Theoretical foundation of sublinear-time algorithms

亚线性时间算法的理论基础

• 批准号: RGPIN-2015-03907
• 负责人: Blais, Eric
• 金额: $ 2.48万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=685397
• 关键词: Theoretical; foundation; 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.**

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