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

点击翻译按钮获取中文摘要

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.