New Directions in the Design of Local Computation Algorithms

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.