Sublinear Algorithms

The ubiquity of large data sets has had a significant impact on the design of algorithms and has led to the emergence of computational models that capture various aspects of massive data computations, most notably the fact that the data is too large to store or view in its entirety. Such models include streaming algorithms, sublinear time algorithms, sublinear query time algorithms with preprocessing, property testing algorithms, distributed algorithms, and massively parallel algorithms. Though each of these models has somewhat different properties, what is common to them is that algorithms compute and make decisions based on only small local portions of the input.

In the streaming setting, big data streams go by, and the algorithm has limited space in which to store information and intermediate computations. Sketching algorithms compress the input in such a way that certain operations can be supported on the sketches. Sublinear time algorithms approximate a parameter of the data after viewing a minuscule fraction of the data. Local algorithms compute and make decisions on parts of the output after considering only a portion of the input. Property testing algorithms quickly determine what properties are held by the data. Local distributed algorithms are such that processors must output a decision based on only a small number of rounds of interaction with only nearby processors, and hence based on inputs within a small local radius. The massively parallel computation model of computation theoretically abstracts parallel cluster computing in practical settings where several commodity-grade computers interact to solve large-scale problems. Distribution testing algorithms understand statistical properties of the data with sublinear samples in the size of the domain.

Sublinear algorithms in the above models have been studied for at least two decades, and a variety of very powerful tools have been developed in each. The past few years have seen a flurry of exciting developments and results, as well as the establishment of new connections between these sublinear models and common algorithmic and analysis techniques. Further, new paradigms have emerged to incorporate new resources, constraints, or objectives to the sublinear setting, ranging from robustness, privacy, and data erasure to interactive proofs and oracle-aided algorithms.

This program brings together researchers from the different communities of sublinear algorithms. After a boot camp that will foster a common language, there will be three workshops that focus on trends that cut across the communities: 1) Extroverted Sublinear Algorithms, 2) Sublinear Graph Simplification, and 3) Local Algorithms.