AF: Small: Local Computation Algorithms

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

The ubiquitousness of massive data sets presents great challenges. The difficulty of dealing with massive data sets is especially formidable when attempting to solve computational problems in which both the inputs and the outputs to the computation are large. In such a situation, it would be useful if one could find faster ways of computing just the portion of the output that is required by the user. This project aims to study "local computation algorithms", namely algorithms that quickly compute only the portions of the output that are required by the user, without performing the full computation. In particular, local computation algorithms view only a miniscule portion of the input. The PI considers a broad based approach, studying the application of local computation algorithms to a range of problems and settings within algorithm design. The focus of this research is on the question of when local computations can be done in time that is sub-linear in the size of the input and output. The proposed research will develop techniques for constructing such algorithms and for understanding when such algorithms are not possible. The project will leverage known results from sub-linear time algorithms, which for the most part have focused on the somewhat different setting of computational problems in which the inputs are large but the outputs are small. In addition, the project will investigate well-studied classes of algorithmic techniques and focus on modifying them for use in this new setting. Such classes include algorithmic techniques first developed for parallel and distributed algorithms, as well as the extensively used greedy method. Problems from combinatorial optimization, graph theory and compressibility of strings will be studied.