AF: Small: The Lowerbounds in the Complexity of Parallelization

University Of Washington, Seattle WA

Investigators

Abstract

The PI investigates a family of techniques applicable to understanding streaming algorithms and static data structures. A common theme is the use of methods from information theory to measure how the information flows in the systems of interest. The main goal is to understand how the complexity of parallelizing these systems. For example, if a static data structure is required to support many users accessing data in parallel, can the data structure be made more efficient in terms of the number of probes per user? How can one measure the parallel complexity? How do the memory requirements for a streaming algorithm change when the algorithm must process many streams in parallel? In all of these questions, an obvious solution is to process each stream or user independently. In this project the PI seeks to understand whether this is optimal in general. The PI has already had significant success in tackling these kinds of questions in the context of communication complexity. The goal of this project is to port methods that work for communication complexity to the domains of streaming algorithms and data structures. This project supports the training of two graduate students in these topics. The PI is also involved in two major workshops on relevant subjects, one at BIRS and one at the Simons institute, as a part of this one-year award.