AF: Small: Local Computation Algorithms -- New Directions and Techniques

大型数据集的处理和分析提出了大量的计算挑战。 为了应对这些挑战，需要新的计算模型来提取海量数据集上计算的本质。 “局部计算算法”（LCA）是PI及其合作者提出的一种新的计算模型。LCA是一种超高效地计算所需输出部分的随机算法。在这个项目中，PI的目标是将LCA扩展到新的前沿领域，如纠错码，矩阵分析，近似算法。PI还计划通过应用其他领域的工具和技术来改进先前的结果，例如Monte Carlo Markov chains，在线和分布式算法以及局部图分割。该项目的更广泛影响包括指导理论计算机科学和其他计算导向科学领域中代表性不足的本科生和研究生。

Processing and analysis of large data sets presents substantial computational challenges. New computational models which distill the essence of computing over massive data sets are needed to address the challenges. "Local computation algorithm" (LCA) is a new computation model proposed by the PI and his collaborators. LCAs are randomized algorithms computing required portion of the output super-efficiently.In this project, the PI aims to extend LCAs to new frontiers such as error correction codes, matrix analysis, approximation algorithms. The PI also plans to improve upon prior results by applying tools and techniques from other fields such as Monte Carlo Markov chains, online and distributed algorithms, and local graph partitioning.The broader impacts of the project include mentoring of undergraduate and graduate students from under-represented groups in theoretical computer science and other computationally-oriented scientific fields.