AF: Small: Sparsity in Local Computation

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

Consider a setting in which inputs to and outputs from a computational problem are so large that there is not enough time to read them in their entirety. However, if a user is interested only in small parts of the output at any given time, it may be possible to provide partial answers to the user in much less time than it would take to compute the whole answer, and even, perhaps, less than the time necessary to read the whole input. Such fast algorithms that compute only the specific parts of the output needed by the user are referred to as "local computation algorithms" (LCAs). There have been many successes at designing such algorithms for a variety of problems. However, most of these successes have been for inputs that are in some sense "sparse" -- for example, for social networks in which the average number of "friends" is small, or optimization problems in which at each decision point there are few possibilities to choose from. This project aims to broaden the scope of these techniques to the more common "dense" scenario. This project will include the organization of a regular workshop "Workshop on Local Algorithms (WOLA)," as well as incorporate training for graduate students, research opportunities for undergraduates, and produce material that is incorporated into the investigator's "Sublinear Time Algorithms" course. In more detail, the goal of the proposed research is to develop new tools for designing LCAs. A main focus of this project is on techniques for designing LCAs for dense problems via sparsification techniques. One success of the field of algorithms has been to show that many computations on dense graphs can be performed by first finding a sparse graph which has approximately the same solution as the dense graph, and then solving the problem on the sparse graph. This project investigates such techniques in the setting of LCAs. Furthermore, this project studies how to do such sparsification in a local manner -- without solving the whole problem up front. For example, this project will develop fast LCAs which allow a user to determine which edges are part of a sparse approximating subgraph of the original graph. The research will mine rich sources of techniques from distributed algorithms, massively parallel computation, and sublinear algorithms. A wide range of optimization problems will be considered, including problems related to finding sparse subgraphs which capture the essential connectivity features of the input graph, coloring, and the class of problems captured by covering and packing linear programs. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.