CAREER: Sublinear Algorithms --- Theory and Applications

世界各地的科学、政府和商业组织积累的现有和新出现的数据数量令人望而生畏。随着所有类型的数据变得更容易获得和存储更便宜，数据集正变得越来越大。因此，需要对海量数据集执行计算任务：比较基因组、压缩媒体文件、搜索大型文档集并将其归类、研究互联网图表以及汇编人口普查数据，仅举几例。这一研究项目的根源在于以下几个领域的基础问题：*在读取所有数据集的成本高得令人望而却步的情况下，我们还能计算出关于数据集的有用信息吗？换句话说，我们可以在时间上做什么？对于大多数有趣的问题，精确的算法必须读取整个输入，因此至少需要线性时间。然而，次线性算法拥有极高效率的近似计算的前景。该奖项将旨在拓宽次线性算法的范围和扩展其适用性的研究活动与旨在在宾夕法尼亚州立大学建立强大的理论计算机科学小组并广泛传播新发现的教育活动相结合。它致力于研究次线性算法的能力的三个一般方向：(1)设计和分析用于各种应用中的具体任务的新的次线性算法，并且需要新的技术；(2)为次线性计算的连贯理论建立基础，重点是算法设计和分析的通用技术，以及新的数据访问模型；(3)在上下文(例如，数据隐私)中利用次线性空间算法可以解决的问题的特殊结构，其中，极端效率本身不是要求，但有助于保证其他特性，例如对数据的微小变化的健壮性。这三个方向的一个共同主题是包含具有实际意义的新问题和新模式。

The amount of existing and newly appearing data accumulated by scientific, governmental and business organizations around the world is daunting. As data of all types gets easier to obtain and cheaper to store, data sets are becoming increasingly large. Consequently, there is a need to perform computational tasks on massive data sets: comparing genomes, compressing media files, searching through and clustering large sets of documents, studying the Internet graph, and compiling census data, to name just a few. This research project has its roots in the following question, fundamental to several fields:* Can we still compute something useful about a data set when reading all of it is prohibitively expensive? In other words, what can we do in time sublinear in the length of the input?For most interesting problems, an exact algorithm provably has to read the entire input, and thus requires at least linear time. However, sublinear algorithms hold the promise of extremely efficient approximate computations.This award integrates research activities aimed at broadening the scope and extending the applicability of sublinear algorithms, with educational activities aimed at building a strong theoretical computer science group at Penn State and broadly disseminating new findings. It pursues three general directions for investigating the power of sublinear algorithms: (1) designing and analyzing new sublinear algorithms for concrete tasks that are used in a variety of applications and require new techniques, (2) building the foundations for a coherent theory of sublinear computation, with the focus on generic techniques for algorithm design and analysis, and new models for data access, (3) exploiting the special structure of problems solvable with sublinear-space algorithms in contexts (e.g., data privacy), where extreme efficiency is not a requirement per se, but helps to guarantee other properties, such a robustness to small changes in the data. A theme common to all three directions is to encompass new problems and models of practical relevance.