AF: Small: More Lowerbounds in the Complexity of Parallelization

该项目探讨了通信复杂性，数据结构和电路复杂性的基本问题。 尽管付出了很多努力，但只有少数几种方法被开发出来用于证明计算模型效率的下限。在这个项目中，PI将研究一系列适用于理解通信复杂性，数据结构和布尔电路复杂性下限的技术。PI将研究关于这些计算模型的长期开放问题，以及尚未被广泛考虑的主题。一个共同的主题是使用信息论的方法来衡量信息如何在感兴趣的计算系统中流动。最近，信息论的方法在这一竞技场中发挥了巨大的优势，本项目旨在进一步探索分析信息流如何有助于理解计算过程的局限性。 PI计划组织一个关于计算机科学中信息论方法的研讨会。

This project explores fundamental questions in communication complexity, data structures and circuit complexity. Despite much effort, only a few methods have been developed for proving lower bounds on the efficiency of computational models. In this project, the PI will study a family of techniques applicable to understanding lower bounds in communication complexity, data structures, and boolean circuit complexity. The PI will study both longstanding open problems regarding these computational models, and topics that have not yet been widely considered. A common theme is the use of methods from information theory to measure how the information flows in the computational systems of interest. Methods from information theory have been used to great advantage in this arena recently, and this project seeks to further explore how analyzing the flow of information can help understand the limits of computational processes. The PI plans to organize a workshop on information theory methods in computer science.