AF: Small: New directions in the design of local computation algorithms

当试图解决输入和输出都很大的计算时，处理大数据是令人敬畏的。尽管如此，通常情况下，在任何阶段都只需要解决方案的一小部分。最近引入了本地计算算法，以便允许用户快速访问所需的输出部分，而无需执行全部计算。局部计算算法的目标是以比查看整个输入或输出的简单任务更快的方式向用户提供有用的答案。建议的研究将扩展局部计算算法的范围，以允许对来自组合优化的新问题进行如此快速的处理。将研究的一类本地计算算法是那些提供对输入图的稀疏子图的查询访问的算法，该稀疏子图保留了原始图的连通性和距离属性。第二类本地计算算法“清理”数据以具有某些所需的属性，例如图的连通性。将开发新的技术来处理基本的计算问题，这些问题可以用作解决广泛的其他问题的工具。该项目的更广泛影响是对年轻研究人员的教育和指导。PI将在当地小学从事计算机科学不插电活动。国际和平协会将积极工作，确保妇女和少数族裔学生更多地参与该项目。来自次线性时间算法的材料将整合到本科生和研究生的算法课程中。

Dealing with big data is formidable when attempting to solve computations in which both the inputs and outputs are large. Nonetheless, frequently it is the case that only small parts of the solution are needed at any stage. Local computation algorithms were recently introduced in order to allow a user to quickly access the portions of the output that are required, without performing the full computation. The aim of local computation algorithms is to provide useful answers to the user in a manner that is significantly faster than what is required even for the simple task of viewing the whole input or output.The proposed research will expand the scope of local computation algorithms to allow such fast processing for new problems from combinatorial optimization. One class of local computation algorithms that will be studied are those that provide query access to a sparse subgraph of the input graph which preserves connectivity and distance properties of the original graph. A second class of local computation algorithms "clean up" data to have certain desirable properties, such as graph connectivity. New techniques will be developed to approach basic computational problems that can be used as tools in solving a wide array of other problems.The broader impacts of this project are in the education and mentoring of young researchers. The PI will engage in Computer Science Unplugged activities at local elementary schools. The PI will work actively to ensure greater participation of women and minority students in the project. Material from sub-linear time algorithms will be integrated into undergraduate and graduate algorithms courses.