CAREER: The power and limitations of randomness

这个项目解决了计算机科学中的三个基本问题：1）伪随机性：什么时候随机性是有效计算所必需的？2)近似的难度：哪些优化问题在计算上是困难的？3)沟通的复杂性：哪些问题可以用很少的沟通来解决？乍一看，这些问题似乎完全不同。然而，通过一个隐藏的、更基本的主题，它们之间存在着强大而深刻的联系：在随机性中识别结构。中心主题是理解随机性和伪随机性在计算中的作用可以指导复杂性理论，通信复杂性，算法设计等问题。拟议的研究有可能影响复杂性理论、优化、流算法、密码学和通信复杂性等多个领域;这些领域反过来又触及计算机科学的几个核心领域，影响所有科学甚至我们的日常生活。例如，伪随机发生器对于节省流算法中的空间是有用的，这反过来对于处理大量数据是重要的，如在许多现代应用中所做的。拟议的研究计划的一个组成部分是教育本科生和研究生。PI计划通过积极指导博士生和本科生的研究项目，让各个层次的学生参与到提案中所概述的研究中来。更详细地说，该项目旨在解决以下三个问题：1）伪随机性：算法中的随机性是否可以以空间中的常数因子增加为代价来消除？最近的工作已经导致解决了一些长期存在的挑战，在这种情况下，新技术可能会导致进一步的进展。2）优化层次结构和近似的硬度：半定规划（SDP）层次结构是算法设计中最强大的技术。能否为近似算法中的问题发展一个全面的理论来理解半定层次的能力和局限性？这是一个特别紧迫的问题，我们没有NP-硬度的结果，是均匀稀疏割的情况下，唯一的游戏问题，或平均情况下的问题，如种植集团问题。解决问题？在这方面研究最多的函数类之一？这样的特性将可能大大简化通信成本分析的任务。上述关键领域之间有着丰富的互动历史，应根据过去几年在各个领域取得的最新进展重新研究这些联系。

This project addresses three foundational questions in computer science: 1) Pseudo- randomness: When is randomness necessary for efficient computing? 2) Hardness of approximation: Which optimization problems are computationally hard? 3) Communication complexity: Which problems can be solved with little communication?At first glance, these questions appear quite disparate. However, there is a strong and deep connection between them through a hidden, more basic, theme: identifying structure in randomness. The central motif is that understanding what role randomness and pseudorandomness have in computation can be a guiding approach to questions in complexity theory, communication complexity, algorithm design, and more. The proposed research has potential for impacting several areas such as complexity theory, optimization, streaming algorithms, cryptography, and communication complexity; these areas in turn touch several core fields of computer science that impact all of science and even our daily lives. For example, pseudorandom generators are useful for saving space in streaming algorithms which in turn are important for processing massive amounts of data as is done in many modern applications. An integral part of the proposed research plan is to educate both undergraduate and graduate students. The PI intends to involve students at all levels in performing the research outlined in the proposal by actively advising PhD students as well as guiding undergraduate students on research projects.In more detail, this project aims to address the following three questions:1) Pseudorandomness: Can randomness in algorithms be removed at the expense of a constant-factor increase in space? Recent work has led to the resolution of several longstanding challenges in this context and the new techniques can potentially lead to further progress.2) Optimization hierarchies and hardness of approximation: Semi-definite programming (SDP) hierarchies are some of the most powerful techniques in algorithm design. Can a comprehensive theory to understand the power and limitations of the semi-definite hierarchies be developed for problems in approximation algorithms? This is a particularly pressing issue for problems where we do not have NP-hardness results as is the case for uniform sparsest cut, the unique games problem, or average-case problems like the planted clique problem.3) Communication complexity: Can we characterize precisely the communication complexity of ?lifted problems??one of the most studied classes of functions in this context? Such a characterization will likely simplify the task of analyzing communication costs significantly. There is a rich history of interaction between the above pivotal areas and these connections should be investigated anew in light of the recent progress in the respective fields over the last few years.