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.