AF: Small: The Lowerbounds in the Complexity of Parallelization

PI研究了一系列适用于理解流算法和静态数据结构的技术。一个共同的主题是使用信息论的方法来测量感兴趣的系统中的信息如何流动。主要目标是了解并行化这些系统的复杂性。例如，如果需要一个静态数据结构来支持许多用户并行访问数据，那么就每个用户的探测数量而言，是否可以使数据结构更有效？如何度量并行复杂度呢？当算法必须并行处理许多流时，流算法的内存需求如何变化？在所有这些问题中，一个明显的解决方案是独立处理每个流或用户。在这个项目中，PI试图了解这是否在一般情况下是最佳的。在通信复杂性的背景下，PI已经在解决这类问题方面取得了重大成功。这个项目的目标是将处理通信复杂性的方法移植到流算法和数据结构领域。本项目支持两名研究生在这些课题上的培训。作为这项为期一年的奖励的一部分，PI还参与了两个有关主题的主要研讨会，一个在BIRS，另一个在Simons研究所。

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.