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.

Project Start
Project End
Budget Start
2014-09-01
Budget End
2017-08-31
Support Year
Fiscal Year
2014
Total Cost
$400,000
Indirect Cost
Name
Massachusetts Institute of Technology
Department
Type
DUNS #
City
Cambridge
State
MA
Country
United States
Zip Code
02139