AF: Small: Local Computation Algorithms

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

The ubiquitousness of massive data sets presentsgreat challenges. The difficulty of dealing with massive datasets is especially formidable when attempting tosolve computational problems in which both the inputsand the outputs to the computation are large.In such a situation, it would be useful if one could findfaster ways of computing just the portion of the output that is requiredby the user.This project aims to study "local computation algorithms",namely algorithms that quickly compute only the portions of theoutput that are required by the user,without performing the full computation.In particular, local computation algorithmsview only a miniscule portion of the input.The PI considers a broad based approach, studying the application oflocal computation algorithms to a range of problems andsettings within algorithm design.The focus of this research is on the question of when local computationscan be done in time that is sub-linear in the size of the input and output.The proposed research will develop techniques for constructingsuch algorithms and for understanding when such algorithms arenot possible.The project will leverage known results from sub-linear timealgorithms, which for the most part have focused on the somewhatdifferent setting of computationalproblems in which the inputs are large but the outputs are small.In addition, the project will investigate well-studiedclasses of algorithmic techniques and focus on modifying them foruse in this new setting. Such classes include algorithmic techniquesfirst developed for parallel and distributed algorithms, as well as theextensively used greedy method.Problems from combinatorial optimization, graph theory and compressibilityof strings will be studied.